题解：最小栈(栈算法)
1.题目
题目链接：LINK
这个题目题意说的有点绕，说白了让你在常数时间内检索到最小元素就是O(1)时间复杂度下找到栈中最小的元素。
2.题解
思路：这个栈可以内嵌套两个库栈来进行解决，一个库栈负责正常入数据，另一个库栈负责在O(1)时间复杂度下找出(记录)栈最小值。
class MinStack { private: stack<int> _normalst; stack<int> _minst; public: MinStack() {} void push(int val) { _normalst.push(val); if(_minst.empty() || _minst.top() >= val) { _minst.push(val); } } void pop() { if(_minst.top() == _normalst.top()) { _minst.pop(); } _normalst.pop(); } int top() { return _normalst.top(); } int getMin() { return _minst.top(); } }; /** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(val); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->getMin(); */
思考：用一个库栈 + 一个变量可以解决这个题目吗？为什么？
答：不能。
因为如果用一个变量去存储最小值，如果栈的最小值被pop掉了，变量很难去更新到次小值。
但是把一个变量去替换为一个栈就不会有这个问题了，因为可以把之前出现的“最小值”都记录下来。
图解如下：
3.总结
思路是关键点。
关键点：最小栈的实现： 两个栈 or 栈+变量？？？
EOF
