原文題目

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

• MinStack() initializes the stack object.
• void push(int val) pushes the element val onto the stack.
• void pop() removes the element on the top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

題目摘要

1. 問題描述：設計一個push(val)、pop()、top()和getMin()四操作的堆疊。
   • push(val)：將元素加入堆疊。
   • pop()：移除堆疊頂端的元素。
   • top()：回傳堆疊頂端的元素。
   • getMin()：回傳堆疊中的最小值。
2. 輸入：若干次操作，如 push(val)、pop()、top()、getMin()，依序對堆疊進行操作。
3. 輸出：對於每個 top() 或 getMin() 操作，回傳相應的結果值。

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

解題思路

1. 定義兩個堆疊：
   • 建立兩個堆疊，一個是 主堆疊stack，用來存儲所有加入的數字。另一個是最小堆疊 minStack，用來追蹤當前堆疊中的最小值。
2. 加入元素並追蹤最小值：
   • 每次執行 push(val) 時，將 val 加入 stack。
   • 接著檢查 minStack 是否為空，或 val 是否小於等於 minStack 的頂部元素。如果是，則將 val 也加入 minStack。這樣可以確保 minStack 記錄著當前的最小值。
3. 取出元素並更新最小值：
   • 當執行 pop() 時，先取得 stack 的頂部元素，檢查這個元素是否與 minStack 的頂部元素相同。如果相同，表示這個元素是當前最小值，因此從 minStack 中同步取出該元素。
   • 最後再從 stack 中取出頂部元素，完成元素的移除。
4. 獲取堆疊頂部元素：
   • top() 操作只需直接回傳 stack 的頂部元素。
5. 獲取最小元素：
   • 執行 getMin() 時，只需回傳 minStack 的頂部元素，因為 minStack 始終保持著堆疊中的最小值。

程式碼

class MinStack {
    //定義兩個堆疊：一個用來存儲所有元素，另一個用來儲存最小值
    private Stack<Integer> stack; //存放所有元素
    private Stack<Integer> minStack; //存放當前的最小值
    //定義兩個堆疊
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    //將元素推入堆疊
    public void push(int val) {
        stack.push(val);
        //如果最小堆疊是空的，或當前元素小於等於最小堆疊的頂部元素，則也將該元素加入最小堆疊
        if(minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }
    //從堆疊中移出頂部元素
    public void pop() {
        //先取得主堆疊的頂部元素
        int top = stack.peek();
        //如果主堆疊頂部元素與最小堆疊頂部元素相等，表示該元素是當前最小值，從最小堆疊中同步取出
        if (top == minStack.peek()) {
            minStack.pop();
        }
        stack.pop();
    }
    //獲取堆疊頂部元素（不取出）
    public int top() {
        return stack.peek();
    }
    //獲取堆疊中的最小元素
    public int getMin() {
        //回傳最小堆疊的頂部元素，即當前堆疊中的最小值
        return minStack.peek();
    }
}

結論： 這題就像你每天疊衣服，除了要把每件衣服放進去，還得隨時知道哪件最薄。為了不浪費時間翻來翻去，你準備了兩個籃子：一個放所有的衣服，另一個只放每次加進來時「最薄的衣服」。這樣，每當你取走一件衣服時，還能快速更新最薄的那件，無論衣服怎麼加減，都能馬上知道目前最薄是哪件。這種方法既方便又省時間，就像有個「記憶超好」的助手，隨時幫你記錄哪件衣服最輕便！