题解：最小栈(栈算法)

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