155. Min Stack

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

algorithm thought

首先min stack有普通stack的接口，能够处理正常stack的数据。所以肯定需要一个stack来充当正常的stack。

不仅如此，还希望能在O(1)时间内返回最小值，这就希望我们保存最小值，如果只用一个值保存，肯定是不行的。因为如果这个最小值被弹出，找到下一个最小值的时间需要O(n)。这里用第二个栈来保存最小值，因为最得到栈中的最小值过程也需要有先进后出的特性。

code

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

    }

    void push(int x) {
        st.push(x);
        if(mist.empty()||x<=mist.top()){
            mist.push(x);
        }
    }

    void pop() {
        if(mist.top()==st.top()){
            mist.pop();
        }
        st.pop();
    }

    int top() {
        return st.top();
    }

    int getMin() {
        return mist.top();
    }
private:
    stack<int> mist;
    stack<int> st;
};

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

algorithm analysis

所有操作时间复杂度都是O(1)的