Min Stack: theo dõi phần tử nhỏ nhất mà không cần quét lại

Đề bài ngắn gọn. Thiết kế một stack trong đó push, pop, top, và getMin đều chạy trong O(1). Ba cái đầu thì hiển nhiên — bất kỳ stack nào cũng làm được trong constant time. getMin mới là phần khó. Không có bookkeeping thêm nào, tính minimum đòi hỏi phải quét toàn bộ phần tử đang có trong stack, tức là O(n). Constraint buộc bạn phải duy trì minimum theo cách incremental, không bao giờ tính lại từ đầu.

Đề bài

Thiết kế class MinStack hỗ trợ push, pop, top, và getMin — trong đó mọi operation, bao gồm cả việc lấy phần tử nhỏ nhất hiện tại trong stack, đều phải chạy trong O(1). Full statement: LeetCode 155.

Ràng buộc:
- -2^31 <= val <= 2^31 - 1
- Các method pop, top và getMin luôn được gọi trên stack không rỗng.
- Tối đa 3 * 10^4 lần gọi đến push, pop, top và getMin.

O(1) thực sự đòi hỏi điều gì

Dải giá trị là -2^31 <= val <= 2^31 - 1 — toàn bộ phạm vi integer 32-bit, bao gồm INT_MIN. Điều đó có ý nghĩa. Bất kỳ approach nào cố mã hóa "không có minimum" bằng sentinel như Integer.MAX_VALUE đều nguy hiểm; một lần push hợp lệ INT_MAX sẽ clobber sentinel đó. Câu trả lời đúng là theo dõi xem cấu trúc minimum-tracking có rỗng không một cách riêng biệt với giá trị nó chứa.

Tối đa 3 * 10^4 lần gọi sẽ được thực hiện. Con số này đủ nhỏ để một getMin O(n) vẫn chạy nhanh trong thực tế. Nhưng bài toán yêu cầu tường minh O(1) cho mỗi operation — đây là bài design, và yêu cầu hiệu năng là constraint cần thỏa mãn, không phải gợi ý để tối ưu. Brute-force scan không đáp ứng yêu cầu; nó trả lời sai.

Bài toán cũng đảm bảo rằng pop, top, và getMin chỉ được gọi trên stack không rỗng. Điều này loại bỏ một họ defensive check khỏi implementation. Bạn không cần xử lý trường hợp stack rỗng khi đọc.

Approach 1: brute force — quét mỗi lần getMin

Cách đọc đơn giản nhất: giữ một list thuần túy, và mỗi khi getMin được gọi, đi qua toàn bộ list và tìm kết quả.

class MinStack:
    def __init__(self):
        self.stack = []
 
    def push(self, val: int) -> None:
        self.stack.append(val)
 
    def pop(self) -> None:
        self.stack.pop()
 
    def top(self) -> int:
        return self.stack[-1]
 
    def getMin(self) -> int:
        return min(self.stack)

public class MinStack {
    private List<int> stack = new List<int>();
 
    public MinStack() { }
 
    public void Push(int val) {
        stack.Add(val);
    }
 
    public void Pop() {
        stack.RemoveAt(stack.Count - 1);
    }
 
    public int Top() {
        return stack[stack.Count - 1];
    }
 
    public int GetMin() {
        int m = stack[0];
        for (int i = 1; i < stack.Count; i++)
            if (stack[i] < m) m = stack[i];
        return m;
    }
}

Đây là đúng. Và cũng bị loại ngay bởi yêu cầu. getMin là O(n) — mỗi lần gọi đều duyệt qua mọi phần tử đang có trong stack. Ba operation còn lại là O(1).

Bài học từ brute force là thông tin bạn đang thiếu: vào thời điểm bạn gọi getMin, bạn cần câu trả lời sẵn sàng, không phải trì hoãn. Điều đó có nghĩa minimum phải được theo dõi khi phần tử đến và đi, không phải tính khi được hỏi.

Complexity: push/pop/top O(1); getMin O(n). Space O(n).

Approach 2: two stacks — giữ một lịch sử minimum song song

Quan sát cốt lõi là minimum của stack chỉ thay đổi khi push (nó có thể giảm) và pop (nó có thể tăng nếu bạn xóa minimum hiện tại). Quan trọng hơn, minimum sau một pop chính xác là minimum trước khi push tương ứng. Đó là một lịch sử. Stack là container tự nhiên cho lịch sử unwind theo thứ tự LIFO.

Vậy: duy trì một stack thứ hai — gọi là min_stack — trong đó đỉnh luôn chứa minimum hiện tại. Khi push(val), nếu val nhỏ hơn hoặc bằng minimum hiện tại, push vào min_stack cũng. Khi pop, nếu giá trị bị xóa bằng minimum hiện tại, pop min_stack cũng.

Dấu <= rất quan trọng. Nếu bạn push 5, 1, 1 và dùng < chặt, chỉ một 1 vào min_stack. Sau đó bạn pop 1 trên cùng từ main stack, code thấy nó bằng min_stack[-1] và pop min_stack — nhưng giờ min_stack rỗng, dù một 1 thứ hai vẫn còn trong main stack. Dùng <= nghĩa là các minimum trùng lặp mỗi cái có slot riêng trong min_stack, nên mỗi pop xóa một bản sao của minimum thì cũng xóa đúng một bản sao tương ứng từ min_stack.

Trace trạng thái: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()

Từng bước:

• push(-2): main_stack thành [-2]. min_stack rỗng, push vô điều kiện -> [-2].
• push(0): main_stack [-2, 0]. 0 > -2, bỏ qua min_stack. Nó vẫn [-2].
• push(-3): main_stack [-2, 0, -3]. -3 <= -2, push -> min_stack là [-2, -3].
• getMin(): return min_stack[-1] = -3. Đúng.
• pop(): giá trị pop là -3. Nó bằng min_stack[-1] = -3, nên pop min_stack cũng. Giờ main_stack là [-2, 0], min_stack là [-2].
• top(): return main_stack[-1] = 0. Đúng.
• getMin(): return min_stack[-1] = -2. Đúng.

Mọi operation chỉ chạm đỉnh của một stack. Constant time trong mọi trường hợp.

class MinStack:
    def __init__(self):
        self.main_stack = []
        self.min_stack = []
 
    def push(self, val: int) -> None:
        self.main_stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)
 
    def pop(self) -> None:
        popped = self.main_stack.pop()
        if popped == self.min_stack[-1]:
            self.min_stack.pop()
 
    def top(self) -> int:
        return self.main_stack[-1]
 
    def getMin(self) -> int:
        return self.min_stack[-1]

public class MinStack {
    private Stack<int> mainStack = new Stack<int>();
    private Stack<int> minStack = new Stack<int>();
 
    public MinStack() { }
 
    public void Push(int val) {
        mainStack.Push(val);
        if (minStack.Count == 0 || val <= minStack.Peek())
            minStack.Push(val);
    }
 
    public void Pop() {
        int popped = mainStack.Pop();
        if (popped == minStack.Peek())
            minStack.Pop();
    }
 
    public int Top() {
        return mainStack.Peek();
    }
 
    public int GetMin() {
        return minStack.Peek();
    }
}

Complexity: Tất cả operations O(1). Space O(n) trong trường hợp xấu nhất — dãy giảm nghiêm ngặt như 5, 4, 3, 2, 1 push mọi phần tử vào cả hai stack. Trong workload mixed trung bình, min_stack nhỏ hơn đáng kể so với main_stack.

Approach 3: single stack với các cặp (value, current-min)

Có một cách khác để gắn minimum vào mỗi phần tử: lưu nó trực tiếp bên cạnh giá trị. Thay vì một integer thuần túy, mỗi slot stack chứa một cặp (val, min_tại_thời_điểm_này). Khi push, bạn tính minimum mới ngay lập tức và bake nó vào cặp. Khi pop, cặp biến mất hoàn toàn — không cần logic đồng bộ giữa hai cấu trúc.

class MinStack:
    def __init__(self):
        self.stack = []
 
    def push(self, val: int) -> None:
        current_min = val if not self.stack else min(val, self.stack[-1][1])
        self.stack.append((val, current_min))
 
    def pop(self) -> None:
        self.stack.pop()
 
    def top(self) -> int:
        return self.stack[-1][0]
 
    def getMin(self) -> int:
        return self.stack[-1][1]

public class MinStack {
    private Stack<(int val, int min)> stack = new Stack<(int, int)>();
 
    public MinStack() { }
 
    public void Push(int val) {
        int currentMin = stack.Count == 0 ? val : Math.Min(val, stack.Peek().min);
        stack.Push((val, currentMin));
    }
 
    public void Pop() {
        stack.Pop();
    }
 
    public int Top() {
        return stack.Peek().val;
    }
 
    public int GetMin() {
        return stack.Peek().min;
    }
}

Trace qua cùng ví dụ: push(-2) lưu (-2, -2); push(0) lưu (0, -2) vì minimum đang chạy vẫn là -2; push(-3) lưu (-3, -3) vì -3 giờ là minimum mới. Sau pop() xóa cặp trên cùng (-3, -3), đỉnh mới là (0, -2) và getMin() trả về -2 đúng. Không có cấu trúc riêng, không có đồng bộ cross-stack — minimum tại mọi trạng thái lịch sử của stack được ghi trong mỗi node.

Complexity: Tất cả operations O(1). Space O(n), nhưng mỗi phần tử giờ chiếm gấp đôi bộ nhớ so với approach brute-force. Stack với 30.000 cặp tốn khoảng 480 KB ở 8 bytes mỗi cặp int — không đáng kể trong thực tế, nhưng constant factor cao hơn cả plain stack (approach 1) lẫn sparse min_stack (approach 2 khi minimum ít thay đổi).

Phân tích edge case chi tiết

Giá trị minimum trùng lặp. Push 1, 2, 1. Sau ba push, min_stack trong approach 2 là [1, 1]. Pop 1 trên cùng: min_stack cũng pop một 1, còn lại [1]. getMin() trả về 1 đúng. Nếu bạn đã dùng < chặt thay vì <=, chỉ một 1 được push vào min_stack, và pop đầu tiên sẽ làm nó rỗng — sai. Trong approach 3, mỗi cặp mang snapshot riêng, nên điều này không bao giờ thành vấn đề.

Phần tử đơn. Push 7, rồi gọi getMin(), rồi pop(). Trong approach 2, push đặt 7 vào cả hai stack. getMin() trả về 7. Popping xóa 7 khỏi cả hai. Trong approach 3, cặp duy nhất là (7, 7). Cả hai xử lý đúng.

Dãy giảm nghiêm ngặt. Push 5, 4, 3, 2, 1. Trong approach 2, mọi push thỏa val <= min_stack[-1], nên min_stack tăng đến cùng kích thước như main_stack. Space worst-case cho approach 2 không tốt hơn approach 3 trong tình huống này — cả hai đều là O(n) dữ liệu dạng cặp.

Toàn giá trị bằng nhau. Push 3, 3, 3. Trong approach 2, min_stack là [3, 3, 3] (vì 3 <= 3 kích hoạt push mỗi lần). Pop một lần: xóa một 3 khỏi cả hai. getMin() = 3. Pop lại: tương tự. Đúng đến cùng.

Biên giới overflow. Các giá trị có thể là -2^31. Python xử lý integer tùy ý natively. Trong C#, so sánh giá trị int trực tiếp an toàn trong toàn bộ phạm vi — không có phép toán số học nào ở đây có thể overflow vì chúng ta chỉ so sánh, không cộng.

Cái nào nên dùng

Trong phỏng vấn, tôi chọn approach 3 (cặp). Đây là lý do.

Approach 2 (two stacks) thanh lịch và được biết đến rộng rãi, nhưng nó có một invariant tinh tế cần duy trì: đồng bộ giữa main_stack và min_stack khi pop. Bạn phải nhớ rằng <= là cần thiết (không phải <), và rằng đồng bộ pop được kích hoạt bởi giá trị bằng nhau, không phải vị trí. Đó là hai quyết định implementation không hiển nhiên. Dưới áp lực phỏng vấn, nơi người ta hay mắc lỗi là logic pop — cụ thể là quên sync min_stack khi minimum bị xóa.

Approach 3 chôn toàn bộ logic vào push. Khi bạn viết current_min = min(val, stack[-1][1]) if stack else val, không còn gì để làm sai. pop, top, và getMin đều là thao tác index một dòng. Bạn có thể xác minh tính đúng đắn bằng cách nhìn: mỗi cặp là một snapshot; pop khôi phục snapshot trước đó tự động.

Nhược điểm là bộ nhớ. Trong approach 2, nếu bạn push một triệu phần tử đều tăng, min_stack vẫn ở kích thước 1 trong khi main_stack tăng lên một triệu. Trong approach 3, mọi phần tử đều mang một trường min bất kể. Với constraint 3 * 10^4 của bài toán thì không thành vấn đề. Với implementation production dưới một hệ thống giao dịch tần số cao push hàng triệu giá mỗi giây, tiết kiệm space của approach 2 trở nên thực sự quan trọng.

Trong code review production, tôi chấp nhận cả hai. Sự khác biệt đủ nhỏ để tôi không phản đối approach 2 — chỉ lưu ý invariant duplicate-minimum trong một comment.

Bảng so sánh

Pattern nền tảng: auxiliary state theo dõi aggregate query

Mental model ở đây mở rộng tốt ra ngoài bài toán này. Khi bạn có một container động (stack, queue, deque) và cần trả lời aggregate query (minimum, maximum, sum, running median) trong O(1), mẹo là duy trì một cấu trúc thứ cấp phản chiếu cấu trúc chính. Cấu trúc thứ cấp cập nhật incremental khi insert và remove — không bao giờ tính lại từ đầu.

Cụ thể với stack, pattern min_stack tổng quát trực tiếp thành max_stack (lật điều kiện so sánh), và với bookkeeping nhiều hơn thành cấu trúc hỗ trợ đồng thời cả getMin và getMax. Với queue, cùng ý tưởng xuất hiện trong "Sliding Window Maximum" (LeetCode 239), nhưng monotonic deque thay thế stack đơn giản vì việc xóa trong queue xảy ra ở đầu, không phải cuối.

Vị trí trong series stack

Đây là bài thứ ba trong series, sau Valid Parentheses (20) và Evaluate Reverse Polish Notation (150). Hai bài kia đã thiết lập stack như cấu trúc để theo dõi context "vừa thấy" và để evaluate expression từ trái sang phải. Min Stack khác về bản chất: nó là bài design thay vì thuật toán. Thách thức không phải là tìm traversal khéo léo — mà là thiết kế data structure thỏa mãn một performance contract.

Max Stack (LeetCode 716) là mở rộng trực tiếp. Giống Min Stack, nhưng bạn cũng cần popMax() — xóa phần tử lớn nhất dù nó đang ở đâu trong stack. Điều đó khó hơn vì maximum có thể không ở trên đỉnh, phá vỡ approach min_stack đơn giản. Nó đòi hỏi ordered set song song với stack.

Implement Queue using Stacks (LeetCode 232) là bài design khác: đạt được FIFO semantics chỉ bằng LIFO primitives. Trick transfer (hai stack, một cho push và một cho pop) cùng hương vị với "dùng auxiliary structure để cấu trúc lại access order."

Sliding Window Maximum (LeetCode 239) đưa ý tưởng min-tracking vào một dạng container khác. Bạn có một cửa sổ trượt kích thước k qua một mảng và cần maximum của mỗi cửa sổ trong O(n) tổng cộng. Monotonic deque là tương đương của min_stack, nhưng được điều chỉnh cho cửa sổ hết hạn thay vì cấu trúc LIFO.

Maximum Frequency Stack (LeetCode 895) là bài hàng xóm phức tạp nhất: pop trả về phần tử được push thường xuyên nhất, với ưu tiên cho phần tử mới nhất khi có tie. Nó đòi hỏi frequency map và một stack-per-frequency — phiên bản phức tạp hơn của pattern "theo dõi aggregate state bên cạnh dữ liệu."