MinStack

题目描述[原题链接][https://www.acwing.com/problem/content/description/90/]

设计一个支持push，pop，top等操作并且可以在O(1)时间内检索出最小元素的堆栈。

• push(x)–将元素x插入栈中
• pop()–移除栈顶元素
• top()–得到栈顶元素
• getMin()–得到栈中最小元素

样例

MinStack minStack = new MinStack();
minStack.push(-1);
minStack.push(3);
minStack.push(-4);
minStack.getMin();   --> Returns -4.
minStack.pop();
minStack.top();      --> Returns 3.
minStack.getMin();   --> Returns -1.

算法描述

定义两个栈，一个存放所有的值，一个存放最小值。每次向栈中添加元素的时候需要判断，最小栈的栈顶值是否小于当前值，小于就压到最小栈中，在之后的弹出操作中，如果弹出的元素在最小栈的栈顶也要被弹出。

C++代码

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> sta;
    stack<int> min;
    MinStack() {
        
    }
    
    void push(int x) {
        sta.push(x);
        if(min.empty()||x<=min.top()){
            min.push(x);
        }
    }
    
    void pop() {
        int val =sta.top();
        sta.pop();
        if(min.top()==val){
            min.pop();
        }
    }
    
    int top() {
        return sta.top();
    }
    
    int getMin() {
        return min.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();
 */

Java代码

class MinStack {
    
    Stack<Integer> sta;
    Stack<Integer> minValue;
    /** initialize your data structure here. */
    public MinStack() {
        sta = new Stack();
        minValue = new Stack();
    }
    
    public void push(int x) {
        sta.push(x);
        if(minValue.empty()||minValue.peek()>=x)minValue.push(x);
    }
    
    public void pop() {
        int x = sta.pop();
        if(x==minValue.peek())minValue.pop();
    }
    
    public int top() {
        return sta.peek();
    }
    
    public int getMin() {
        return minValue.peek();
    }
}

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