Pattern · Ngăn xếpTrung bình
Ngăn Xếp Có getMinMin Stack
Hiểu bài
Thiết kế một ngăn xếp (stack) hỗ trợ 4 thao tác, tất cả phải chạy O(1): push(val), pop(), top() (xem đỉnh) và getMin() (lấy phần tử nhỏ nhất đang có).
ts
push(-2); push(0); push(-3)
getMin() // -3
pop()
top() // 0
getMin() // -2Thử thách nằm ở getMin() O(1): không được quét lại toàn bộ mỗi lần hỏi.
Mẹo là nhớ sẵn giá trị nhỏ nhất tại từng tầng của ngăn xếp.
Cách cơ bản
getMin O(n) mỗi lần gọi, các thao tác khác O(1)ts
class MinStackNaive {
private stack: number[] = []
push(val: number) { this.stack.push(val) }
pop() { this.stack.pop() }
top() { return this.stack[this.stack.length - 1] }
getMin() {
// Quét toàn bộ ngăn xếp mỗi lần gọi
return Math.min(...this.stack)
}
}Vì sao cách này chậm:
push/pop/top thì nhanh, nhưng getMin phải duyệt lại toàn bộ phần tử mỗi lần → O(n).
Đề yêu cầu O(1) nên cách này không đạt.
Mở khoá để xem lời giải tối ưu, chạy thử từng bước và câu hỏi liên quan
Xem đầy đủ chạy thử từng bước, Big-O, trường hợp biên và biến thể công ty Việt Nam.