LeetCode 155. Min Stack

題目

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

push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. getMin() -- Retrieve the minimum element in the stack.

    Example:
    MinStack minStack = new MinStack(); // stack = [];
    minStack.push(-2);                  // stack = [-2];
    minStack.push(0);                   // stack = [-2,0];
    minStack.push(-3);                  // stack = [-2,0,-3];
    minStack.getMin();   --> Returns -3. // stack = [-2,0,-3]
    minStack.pop();                      // stack = [-2,0]，移除-3
    minStack.top();      --> Returns 0.  // stack = [-2,0]
    minStack.getMin();   --> Returns -2. // stack = [-2,0]

翻譯

設計一個支援 push, pop, top 以及在常數時間找出最小值的方法getMin, 也就是說getMin這個方法的時間複雜度為O(1)。

push(x) -- 將元素x加入stack上面 pop() -- 移除stack最上面的元素 top() -- 取得stack最上面的元素(不移除) getMin() -- 取得stack裡面最小的元素(不移除)

思路

這題沒有提供javascript，改用java解，一開始打算無視時間複雜度, getMin的時候就跑迴圈來找出最小值，不過這樣超過時間沒辦法通過測試，這邊寫法請看下面失敗的寫法

上網搜尋後發現這個解法簡單易懂，以下分享學習：

1. 首先使用一個變數min來儲存stack中最小的值，這樣getMin()就符合O(1)，速度會快很多
2. 因此就要改成在push跟pop的地方動手腳，push的時候，如果加入的x小於等於min，除了讓min=x，我們還先把目前的min加到stack中
3. 以下用[2,3]這個堆疊作範例，目前min = 2， stack.push(1)，1小於2，所以將2先加入stack再把1加入，stack=[2,3,2,1]
4. 如此一來getMin()的時候會直接回傳1，對top()這個方法也沒任何的影響，但是pop()的時候就會有問題了
5. stack.pop()移除最上面的元素，stack=[2,3,2]，跟正確的stack=[2,3]明顯是不一樣的，而且min也沒更新為2
6. 這時候之前多放入的第二小的數[2]，就發揮作用了，讓min = 2，然後再把這個2移除，stack = [2,3]，min也變成了2，重此之後世界又恢復了和平

解題

public class MinStack {
    Stack<Integer> stack;

    // 使用一個min來紀錄stack中最小的值，注意這邊的min不能用Integer
    // Integer == Integer 的比對方法只保證再-128~127之間會有正確的結果
    int min = Integer.MAX_VALUE; 

    /** initialize your data structure here. */
    public MinStack() {
        this.stack = new Stack<>();
    }

    public void push(int x) {
        //如果x <= min，先將目前的min放入stack後面，再放入x
        if(x <= min){
            this.stack.push(min);
            this.min = x;
        } 
        this.stack.push(x);
    }

    public void pop() {
        // 如果取出的值剛好就是min，因為之前我們把第二小的數放在min前面，所以現在他又變成min了
        if(stack.peek() == this.min){
           //因為之前x<=min的時候也壓了第二小的數進來，所以他也要被pop
           this.stack.pop();
           min =  this.stack.pop();  
        } else {
           this.stack.pop();
        }

    }

    public int top() {
        return this.stack.peek();
    }

    public int getMin() {
        return min;
    }
}

超出時間的寫法

public class MinStack {
    Stack<Integer> stack;

    public MinStack() {
        this.stack = new Stack<>();
    }

    public void push(int x) {
        this.stack.push(x);
    }

    public void pop() {
        if(!stack.empty()){
           this.stack.pop();
        }
    }

    public Integer top() {
        if(!stack.empty()){
           return this.stack.peek();
        } else {
           return null;
        }
    }

    //跑迴圈找出最小值
    public int getMin() {
        int min = Integer.MAX_VALUE;
        Stack<Integer> keep = new Stack<>();

        while(!stack.empty()){
            int v = stack.pop();
            min = v < min ? v : min;
            keep.push(v);
        }

        while(!keep.empty()){
            stack.push(keep.pop());
        }
        return min;
    }
}