155.最小栈

[youzouzou]

题号155：

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) -- 将元素x推入栈中。

pop() -- 删除栈顶的元素。

top() -- 获取栈顶元素。

getMin() -- 检索栈中的最小元素。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.

解题思路：

一开始想用一个变量存储最小元素，但显然，当这个元素被弹出栈后，再要获取最小元素，就不可能满足题目要求的常数时间（我只能想到遍历栈，时间复杂度O(n) ）。所以另外建了个顺序栈s2，当输入的数值比顺序栈栈顶元素小，则push为新的栈顶（因为出栈是按顺序的，所以只要保存比栈顶元素小的输入值即可，不必保存所有值）。在元素出栈时，也需要对顺序栈做出栈处理。

代码实现：

class MinStack {

public:

    /** initialize your data structure here. */

    stack<int> s1,s2;

    MinStack() {}



    void push(int x) {

        s1.push(x);

        if(!s2.size())

            s2.push(x);

        else if(s2.top()>=x)

            s2.push(x);

    }

    

    void pop() {

        int p=s1.top();

        s1.pop();

        if(p==s2.top())

            s2.pop();

    }

    

    int top() {

        return s1.top();

    }

    

    int getMin() {

        return s2.top();

    }

};



/**

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

 */