LeetCode：面试题 03.02. 栈的最小值

题目链接：https://leetcode-cn.com/problems/min-stack-lcci/

解题思路：

1. 通过新建两个栈，一个是数据栈，另一个是临时栈用于存放栈的最小元素；

2. 这里入栈应该将x直接入stk栈；

3. 临时栈判断是否为空，若空则直接入栈，否则将临时栈的栈顶与当前入栈元素x对比，x小于栈顶元素，则入栈；x大与栈顶元素则将较小的栈顶元素入栈；

4. 弹出时，将两个栈都pop；

5. 返回栈的最小元素时，由于临时栈从栈底到栈顶，是按照降序排列，返回栈顶元素即为最小值。

另外一种方法：

主要区别是在入栈时，小于临时栈顶元素，则不入栈，这时两个栈的元素数量不一致。

在弹出元素时，通过判断数据栈的栈顶元素是否与临时栈相同，相同则弹出临时栈的栈顶元素，否则不变；

方案一和方案二其实都是用stackMin栈保存着stackData 每一步的最小值。共同点是
所有操作的时间复杂度都为0(1)、空间复杂度都为0(n)。

区别是:

方案一中stackMin压入时稍省空间，但是弹出操作稍费时间;

方案二中stackMin压入时稍费空间，但是弹出操作稍省时间。

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() 
    {}
    std::stack<int> stk; //局部变量return之后 变量失效；
    std::stack<int> tmp; 
    
    void push(int x) 
    {
        if (tmp.empty())
        {
            tmp.push(x);
        }
        else if (tmp.top() > x)
        {
            tmp.push(x);
        }
        else 
        {
            tmp.push(tmp.top());
        }
        stk.push(x);
    }
    
    void pop() 
    {
        stk.pop();
        tmp.pop();
    }
    
    int top() 
    {
        int i=stk.top();
        return i;
    }
    
    int getMin() 
    {
        return tmp.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();
 */