MinStackOPT2 [source code]

public class MinStackOPT2 {
static
/******************************************************************************/
public class MinStack {
    int min = Integer.MAX_VALUE;
    Stack<Integer> stack = new Stack<Integer>();
    public void push(int x) {
        // only push the old minimum value when the current 
        // minimum value changes after pushing the new value x
        if (x <= min) {          
            stack.push(min);
            min = x;
        }
        stack.push(x);
    }

    public void pop() {
        // if pop operation could result in the changing of the current minimum value, 
        // pop twice and change the current minimum value to the last minimum value.
        if (stack.pop() == min) min = stack.pop();
    }

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

    public int getMin() {
        return min;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        MinStackOPT2.MinStack minStack = new MinStackOPT2.MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println(minStack.getMin()); //-3
        minStack.pop();
        System.out.println(minStack.top()); //0
        System.out.println(minStack.getMin()); //-2
    }
}

这个是discussion上面另外一个很聪明的解法;

这个解法其实比那个存gap的解法要稍微讲道理一些的, 这个解法其实就是直接看出了这个问题的难点: 假如当前这个pop导致min的改变, 那么我们就不知道之前的min是什么了; 这里的做法很直接, 既然你害怕不知道, 我就直接push到下面, 这样你如果pop出来的这个发现跟当前的min相等, 你就知道你只要再pop一个就会得到上一个min: 然后你就可以把这个当初冗余push进来的min pop出来, 并作为新的min;

这个是discussion另外一个解:

class MinStack {  
    private Node head;  

    public void push(int x) {  
        if(head == null)   
            head = new Node(x, x);  
        else   
            head = new Node(x, Math.min(x, head.min), head);  
    }  

    public void pop() {  
        head = head.next;  
    }  

    public int top() {  
        return head.val;  
    }  

    public int getMin() {  
        return head.min;  
    }  

    private class Node {  
        int val;  
        int min;  
        Node next;  

        private Node(int val, int min) {  
            this(val, min, null);  
        }  

        private Node(int val, int min, Node next) {  
            this.val = val;  
            this.min = min;  
            this.next = next;  
        }  
    }  
}

同样是用wrapper的思路来做的, 不过他整个连Stack都不要了, 直接自己做一个LinkedList来作为Stack;

这个用两个Stack的方法才是这个题目最常规的解法:

private Stack<Integer> mStack = new Stack<Integer>();  
private Stack<Integer> mMinStack = new Stack<Integer>();  

public void push(int x) {  
    mStack.push(x);  
    if (mMinStack.size() != 0) {  
        int min = mMinStack.peek();  
        if (x <= min) {  
            mMinStack.push(x);  
        }  
    } else {  
        mMinStack.push(x);  
    }  
}  

public void pop() {  
    int x = mStack.pop();  
    if (mMinStack.size() != 0) {  
        if (x == mMinStack.peek()) {  
            mMinStack.pop();  
        }  
    }  
}  

public int top() {  
    return mStack.peek();  
}  

public int getMin() {  
    return mMinStack.peek();  
}

可惜我没有想到; 说白了, 你害怕pop了之后不知道下一个min应该是多少, 那么存起来就行了, 历史信息的处理和读取而已;

Problem Description

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();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); .
minStack.pop();
minStack.top();
minStack.getMin(); .
Difficulty:Easy
Total Accepted:132.3K
Total Submissions:468.1K
Contributor: LeetCode
Companies
google uber zenefits amazon snapchat bloomberg
Related Topics
stack design
Similar Questions
Sliding Window Maximum

/**

• Your MinStack object will be instantiated and called as such:
• MinStack obj = new MinStack();
• obj.push(x);
• obj.pop();
• int param_3 = obj.top();
• int param_4 = obj.getMin();
  */