MinStack1 [source code]

public class MinStack1 {
static
/******************************************************************************/
public class MinStack {
    private Stack<Integer> stack = new Stack<>();
    private Integer min;
    private int minCount = 0;

    /** initialize your data structure here. */
    public MinStack() {

    }

    public void push(int x) {
        stack.push(x);
        if (min == null) {
            min = x;
            minCount++;
        } else if (x < min) {
            min = x;
            minCount = 1;
        } else if (x == min) {
            minCount++;
        }
    }

    public void pop() {
        int top = stack.pop();
        if (top == min) {
            if (--minCount == 0) {
                min = Integer.MAX_VALUE;
                for (Integer i : stack) {
                    if (i < min) {
                        min = i;
                        minCount = 0;
                    }
                    if (i == min) minCount++;
                }
            }
        }
    }

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

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

    public static void main(String[] args) {
        MinStack1.MinStack minStack = new MinStack1.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
    }
}

这个题目本身是很简单的, 就是怎么提速;

这种implement data structure的问题, 最后的难点其实就在于你在这个数据结构内部选择维护什么样的internal data structures. 这里我的选择是两个int和一个Stack就行了; minCount的作用其实就是防止min有duplicate的情况;

首先想笨办法, 这题的笨办法很直接, 就是Stack照常做, 但是getMin的时候专门走一个pass得到min就行了; 但是这样速度就很慢;
那么一个简单的想法就是维护min, 但是有一个问题, 可能有multiple copies of min, 所以还要维护一个count;
当然这个其实并没有解决所有的问题, 如果当前的count一直被pop到0了怎么办? 当然你可以再多维护几个, 第二小的, 第三小的, 但是这么搞就没有意思了; 我的做法是一旦当前的"最小的"被pop完了, 就重新iterate, 找到一个新的min和其对应的count就行了;

最后的速度是110ms (71%), 可以接受;

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();
  */