第一讲：包含min函数的栈

题目：AcWing 41. 包含min函数的栈
设计一个支持push，pop，top等操作并且可以在O(1)时间内检索出最小元素的堆栈。

push(x)–将元素x插入栈中
pop()–移除栈顶元素
top()–得到栈顶元素
getMin()–得到栈中最小元素
数据范围
操作命令总数 [0,100]。

样例

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.

题目分析：
这道题如果没有返回最小值那么我们可以直接使用栈，那么如果需要返回最小值呢？
我们可以使用辅助栈
辅组栈只保存比栈顶元素小的元素，那么辅助栈的栈顶就是当前栈的最小值。
根据观看下图我们可以很直观感受到栈和辅助栈的关系。
即使 3 弹出栈，那么 41 将成为当前栈最小的值。

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

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