155. 最小栈

解题思路

利用数组可以最小成本的实现栈，主要是看最小元素的查找方式，最简单的方式就是遍历数组，找到最小值。

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

/**
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function (val) {
  this.stack.push(val)
}

/**
 * @return {void}
 */
MinStack.prototype.pop = function () {
  return this.stack.pop()
}

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

/**
 * @return {number}
 */
MinStack.prototype.getMin = function () {
  let length = this.stack.length

  if (!length) return

  let minVal = this.stack[0]

  for (let i = 0; i < length; i++) {
    if (this.stack[i] < minVal) {
      minVal = this.stack[i]
    }
  }

  return minVal
}

在官方中还提供了另外 3 中解题思路：

• 利用辅助栈，在 push 的时候判断当前元素是否小于辅助栈中最小值，如果小于则将当前元素入栈，同时在出栈的时候判断当前元素是否等于辅助栈中最小值，如果是则将辅助栈中的最小值出栈。
• 另一种方式是栈中的每个节点同时保存当前节点的值和栈内最小值。
• 最后一种方式是利用链表自定义一个栈，链表中的每个节点保存当前节点的值、栈内最小值以及上一个节点。

详情可点击查看更多 (opens new window)。

参考

-155. 最小栈 - 力扣（LeetCode） (opens new window)