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();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

---

本题要实现一个最小栈，使得push, pop, top以及getMin都是以O(1)的时间完成。

这是一个非常经典的双栈法题目，我居然不知道。同时使用两个栈，一个普通的用于存放所有数据allStack，另一个只用于存储最小值序列minStack。 push的时候，每次都把x push进allStack。如果minStack为空，则是第一次push，要把x push进minStack；如果minStack非空，则当x小于等于minStack栈顶时，可以把x push进minStack。注意当x等于minStack栈顶的时候也是需要进栈的，因为有可能有重复元素，比如对0,1,0依次进栈，遇到后面的0时，minStack只有前一个0，此时如果后一个0不进栈，如果下一步是pop的话，就会把minStack中的上一个0 pop掉，那么此时getMin时就会出错，因为此时minStack里没东西了，但allStack还保留着0和1，正确的最小值应该是前一个0。 pop时，allStack正常pop。如果pop出来的值等于minStack的栈顶，则minStack也需要pop。 top就取allStack的top。 getMin就取minStack的top。 完整代码如下：

class MinStack {
private:
    stack<int> allStack, minStack;

public: /** initialize your data structure here. */
    MinStack() {}
    void push(int x)
    {
        if (minStack.empty()) {
            minStack.push(x);
        }
        else if (x <= minStack.top()) { // 注意是<=而不是<
            minStack.push(x);
        }
        allStack.push(x);
    }
    void pop()
    {
        int top = allStack.top();
        allStack.pop();
        if (top == minStack.top()) {
            minStack.pop();
        }
    }
    int top() { return allStack.top(); }
    int getMin() { return minStack.top(); }
};

本代码提交AC，用时29MS。

二刷。其实可以更简单一点，辅助的minStack大小始终和allStack一样，当新入元素小于minStack栈顶元素时，自然入minStack；否则，就把minStack栈顶的元素再入一次栈。这样就使得两个栈的大小一样，pop的时候可以同时pop，减少了各种if判断。
完整代码如下：

class MinStack {
private:
    stack<int> allStack, minStack;
public: /** initialize your data structure here. */
    MinStack() {}
    void push(int x)
    {
        if (minStack.empty() || x < minStack.top()) {
            minStack.push(x);
        }
        else {
            minStack.push(minStack.top());
        }
        allStack.push(x);
    }
    void pop()
    {
        allStack.pop();
        minStack.pop();
    }
    int top() { return allStack.top(); }
    int getMin() { return minStack.top(); }
};

本代码提交AC，用时29MS。