包含 min 函数的栈

2022-02-08 数据结构与算法 #JavaScript #栈

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof

初见

复杂度都是 O(1)，所以不能使用比较查找等与栈的长度有关的操作。因此，最小值必须被记录下来，使得每次查询最小值时都能够直接返回。

单纯只记录下最小值还不行，这样的话在最小值出栈后，为了找到新的最小值，就不得不对栈进行遍历，使得 pop() 方法没法达到 O(1)。

需要把最小值、最小值入栈之前的最小值（次小值）、次次小值……都存下来，同时还得保证最小值在这一堆数中位于较固定的位置（有点拗口，直接看答案应该就明白了）。

结论就是使用一个辅助栈，专门用于保存最小值。

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

MinStack.prototype.push = function (x) {
  this.stack.push(x)

  // 如果 minStack 为空（即 x 是第一个入栈元素）或者 x <= 最小值，则 x 也加入 minStack
  if (
    this.minStack.length === 0 ||
    x <= this.minStack[this.minStack.length - 1]
  ) {
    this.minStack.push(x)
  }
}

MinStack.prototype.pop = function () {
  x = this.stack.pop()

  // 如果出栈的是最小值，则 minStack 也要把最小值出栈
  if (x === this.minStack[this.minStack.length - 1]) {
    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]
}

// 测试用例
var obj = new MinStack()
obj.push(x)
obj.pop()
console.log(obj.top())
console.log(obj.min())

因为可能有多个同为最小值的元素（如 [0, 1, 0, 0]），故 minStack 入栈判断条件是 <= 而不是 <。

如果再额外维护一个数值栈，对应保存 minStack 中每个元素在栈中的个数，就能以更新数值栈对应元素个数代替在 minStack 中保存重复的最小值，从而节省一些内存（猜的）。

Chipmunk & Panda

-- 鼠熊部落格

包含 min 函数的栈

初见