Skip to main content

包含min函数的栈（02.栈的最小值）

30. 包含 min 函数的栈（02. 栈的最小值）​

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例​

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.

解题思路​

根据题意，我们需要在常量级的时间内找到最小值！

这说明，我们绝不能在需要最小值的时候，再做排序，查找等操作来获取！

所以，我们可以创建两个栈，一个栈是主栈 stack，另一个是辅助栈 minStack，用于存放对应主栈不同时期的最小值。

图解演示​

代码​

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

MinStack.prototype.push = function (x) {
  this.stack.push(x)
  this.minStack.push(Math.min(this.minStack[this.minStack.length - 1], x))
}

MinStack.prototype.pop = function () {
  this.stack.pop()
  this.minStack.pop()
}

MinStack.prototype.top = function () {
  return this.stack[this.stack.length - 1]
}

MinStack.prototype.min = function () {
  return this.minStack[this.minStack.length - 1]
}