单调栈
解题思路
借用一个辅助栈 min_stack 用于存获取 stack 中最小值；
算法流程：
push()： 每当 push 新值进来时，如果小于等于 min_stack 栈顶值，则一起 push 到 min_stack ，即更新了栈顶最小值，如果大于栈顶值则将栈顶值 push 进 min_stack 占位；pop()： stack 和 min_stack 一起 pop 出去；getMin()： 返回 min_stack 栈顶即可；min_stack 作用分析：
- min_stack 等价于遍历 stack 所有元素，把升序的数字都删除掉，留下一个从栈底到栈顶非严格降序的栈；
- 相当于给 stack 中的降序元素做了标记，每当 pop 这些降序元素，min_stack 会将相应的栈顶元素 pop 出去，保证其栈顶元素始终是 stack 中的最小元素；
图解
复杂度
-
时间复杂度：
O(1)，压栈，出栈，获取最小值的时间复杂度都为O(1)； -
空间复杂度：
O(N)，包含 N 个元素辅助栈占用线性大小的额外空间；
代码实现
var MinStack = function () {
this.stack = [];
this.min_stack = [Infinity];
};
// stack正常push，min_stack只会push需要入栈和栈顶中较小的元素
MinStack.prototype.push = function (x) {
this.stack.push(x);
this.min_stack.push(Math.min(this.min_stack[this.min_stack.length - 1], x));
};
// stack正常pop，min_stack正常pop
MinStack.prototype.pop = function () {
this.stack.pop();
this.min_stack.pop();
};
// 返回stack栈顶元素
MinStack.prototype.top = function () {
return this.stack[this.stack.length - 1];
};
// 返回min_stack栈顶元素
MinStack.prototype.getMin = function () {
return this.min_stack[this.min_stack.length - 1];
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 232. 用栈实现队列
上一篇
评论
