LeetCode-155 最小栈 题解

题目

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

• push(val) —— 将元素 val 推入栈中。
• pop() —— 删除栈顶的元素。
• top() —— 获取栈顶元素。
• getMin() —— 检索栈中的最小元素。

示例

输入：

["MinStack","push","push","push","getMin","pop","top","getMin"]

[[],[-2],[0],[-3],[],[],[],[]]
复制代码

输出：

[null,null,null,null,-3,null,0,-2]
复制代码

解释：

MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.getMin();   --> 返回 -3.

minStack.pop();

minStack.top();      --> 返回 0.

minStack.getMin();   --> 返回 -2.
复制代码

方法

• 辅助栈
  • 同步
  • 非同步
• 差值
• 二维数组
• 扩展运算符（…）
• push() 方法作为对象，同时存储 val 和最小值的信息

解法一

辅助栈—同步

思路

代码

var MinStack = function() {
  this.stack = []
  this.min_stack = []
};

//将元素 val 推入栈中
MinStack.prototype.push = function(val) {
    this.stack.push(val);
    if(!this.min_stack.length){
        this.min_stack.push(val);
    }else{
        this.min_stack.push(val < this.min_stack[this.min_stack.length - 1] ? val : this.min_stack[this.min_stack.length - 1]);
    }
};
//删除栈顶的元素
MinStack.prototype.pop = function() {
    this.stack.pop();
    this.min_stack.pop();
};
//获取栈顶元素
MinStack.prototype.top = function() {
    return this.stack[this.stack.length - 1];
};
//检索栈中的最小元素
MinStack.prototype.getMin = function() {
    return this.min_stack[this.min_stack.length - 1];
};
复制代码

辅助栈—非同步

思路

代码

var MinStack = function() {
  this.stack = []
  this.min_stack = []
};

// 将元素 val 推入栈中
MinStack.prototype.push = function(val) {
  if(this.stack.length === 0 || val <= this.min_stack[this.min_stack.length-1]) {
    this.min_stack.push(val)
  }
  this.stack.push(val)  
};
// 删除栈顶的元素
MinStack.prototype.pop = function() {
  if (this.stack.pop() === this.min_stack[this.min_stack.length - 1]) {
    this.min_stack.pop()
  } 
};
// 获取栈顶的元素
MinStack.prototype.top = function() {
  return this.stack.length > 0 ? this.stack[this.stack.length-1] : null
};
// 检索栈中的最小元素
MinStack.prototype.getMin = function() {
  return this.min_stack[this.min_stack.length - 1]
};
复制代码

解法二

差值

代码 ??

var MinStack = function() {
  this.stack = [];
  this.minVal = Number.MAX_VALUE;
};

// 将元素 val 推入栈中
MinStack.prototype.push = function(val) {
  const minVal = this.minVal;
  if (val < this.minVal) {
    this.minVal = val;
  }
  return this.stack.push(val - minVal);
};
// 删除栈顶的元素
MinStack.prototype.pop = function() {
  const minVal = this.minVal;
  if (this.stack.pop() < 0) {
    this.minVal = minVal - this.stack.pop();
    return minVal;
  }
  return this.stack.pop() + minVal;
};
// 获取栈顶的元素
MinStack.prototype.top = function() {
  const minVal = this.minVal;
  if (this.stack[this.stack.length - 1] < 0) {
    return minVal;
  }
  return this.stack[this.stack.length - 1] + minVal;
};
// 检索栈中的最小元素
MinStack.prototype.min = function() {
  return this.minVal;
};
复制代码

解法三

二维数组

代码

var MinStack = function() {
    this.stack = []
};

// 将元素 val 推入栈中
MinStack.prototype.push = function(val) {
    this.stack.unshift([
    val, 
    Math.min(this.stack[0] ? this.stack[0][1] : Infinity, val)
    ])
};
// 删除栈顶的元素
MinStack.prototype.pop = function() {
    this.stack.shift()
};
// 获取栈顶的元素
MinStack.prototype.top = function() {
    return this.stack[0][0]
};
// 检索栈中的最小元素
MinStack.prototype.getMin = function() {
    return this.stack[0][1]
};
复制代码

解法四

扩展运算符（…）

代码

var MinStack = function() {
    this.stack = []
};

// 将元素 val 推入栈中
MinStack.prototype.push = function(val) {
    this.stack.push(val)
};
// 删除栈顶的元素
MinStack.prototype.pop = function() {
    this.stack.pop()
};
// 获取栈顶的元素
MinStack.prototype.top = function() {
    return this.stack[this.stack.length-1]
};
// 检索栈中的最小元素
MinStack.prototype.getMin = function() {
    return Math.min(...this.stack)
};
复制代码

解法五

push() 方法作为对象

代码

var MinStack = function() {
  this.stack = []
};
// 将元素 val 推入栈中
MinStack.prototype.push = function(val) {
  this.stack.push (
    {
    val: val,
    min: this.stack.length ? Math.min(val, this.getMin()) : val
    }
  )
}
// 删除栈顶的元素
MinStack.prototype.pop = function() {
  this.stack.pop()
}
// 获取栈顶的元素
MinStack.prototype.top = function() {
  return this.stack[this.stack.length - 1].val
}
// 检索栈中的最小元素
MinStack.prototype.getMin = function() {
  return this.stack[this.stack.length - 1].min
}
复制代码