Open
Description
辅助栈
- stack 支持常规的 push、pop、top 操作。
- 定义一个辅助栈 resStack ，将最小值一直保持在栈顶，来支持常数时间复杂度获取。
const MinStack = function() {
this.stack = [];
this.resStack = [Infinity];
};
MinStack.prototype.push = function(x) {
this.stack.push(x);
this.resStack.push(Math.min(this.resStack[this.resStack.length - 1], x));
};
MinStack.prototype.pop = function() {
this.stack.pop();
this.resStack.pop();
};
MinStack.prototype.top = function() {
return this.stack[this.stack.length - 1];
};
MinStack.prototype.getMin = function() {
return this.resStack[this.resStack.length - 1];
};- 时间复杂度: O(1)
- 空间复杂度: O(n)