155. Min Stack - Medium

前往題目

想法

• 題目要求每個方法都要O(1)時間，如果用一般的stack來做的話那push，pop，和top都可以輕易做到。但是還有一個getMin，他要回傳stack中最小的數，如果只用一個int來追蹤的話那萬一這個最小值被pop了，就不知道下一個最小值是多少了，在哪裡都有可能。所以這裡應該需要一個PriorityQueue來儲存
• 但是這樣又有一個問題，pop的時候中間值可能不見了，那就還要再花O(n)時間在priorityQueue裡面搜尋這個東西然後刪掉…

搬運一下前幾個月做這題的想法

• 這題普通，有想到，但沒實作
• 這題有個關鍵點是第二個stack，紀錄最小值的那個，每次有新的值要push的時候都要檢查是否top element比較小，是的話就再push一次top element。這是因為那個值會先被pop掉，因為他比較大，而不會影響到getMin，所以再push一個，這樣pop的時候就不會出現誤差了。Pop的部分兩個stack都是同時Pop
• 有個更好的解釋，直接畫兩個stack，你就可以看到兩個對應的層數就是pop到該數時，該stack的min
• 看不懂的話直接丟debugger看
• 簡單的push -2 0 -3就可以看出來
• 還有一個更省空間的解法，只需一個stack，算差值的

思路

1. 兩個stack，一個紀錄最小值，一個就是主要的stack
2. 每次push的時候，主要的stack直接push就好，最小值stack看看最上層是否比新的值還要小，如果比較小再push一個舊的值，否則新的值。這代表的是每個值所對應的最小值
3. 其他就是直覺的操作

Code

官神解答

class MinStack {

    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<Integer>();
        minStack = new Stack<Integer>();
    }
    
    public void push(int val) {
        stack.push(val);

        if (minStack.empty()) {
            minStack.push(val);
        } else {
            minStack.push(Math.min(val, minStack.peek()));
        }
    }
    
    public void pop() {
        stack.pop();
        minStack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}