题目描述:设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。
思路:维护一个递减栈,并在添加和删除时同时对递减栈进行操作。
const MinStack = function() {
this.stack = [];
// 定义辅助栈
this.stack2 = [];
};
/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function(x) {
this.stack.push(x);
// 若入栈的值小于当前最小值,则推入辅助栈栈顶
if(this.stack2.length == 0 || this.stack2[this.stack2.length-1] >= x){
this.stack2.push(x);
}
};
/**
* @return {void}
*/
MinStack.prototype.pop = function() {
// 若出栈的值和当前最小值相等,那么辅助栈也要对栈顶元素进行出栈,确保最小值的有效性
if(this.stack.pop() == this.stack2[this.stack2.length-1]){
this.stack2.pop();
}
};
/**
* @return {number}
*/
MinStack.prototype.top = function() {
return this.stack[this.stack.length-1];
};
/**
* @return {number}
*/
MinStack.prototype.getMin = function() {
// 辅助栈的栈顶,存的就是目标中的最小值
return this.stack2[this.stack2.length-1];
};