题解:最小栈(栈算法)
目录
- 1.题目
- 2.题解
- 3.总结
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