155. Min Stack

https://leetcode.cn/problems/min-stack/solutions/9036/min-stack-fu-zhu-stackfa-by-jin407891080

解题思路：

借用一个辅助栈 min_stack，用于存获取 stack 中最小值。

算法流程：

push() 方法：每当push()新值进来时，如果小于等于 min_stack 栈顶值或者为第一个元素时，则一起 push() 到 min_stack，即更新了栈顶最小值；
pop() 方法：判断将 pop() 出去的元素值是否是 min_stack 栈顶元素值（即最小值），如果是则将 min_stack 栈顶元素一起 pop()，这样可以保证 min_stack 栈顶元素始终是 stack 中的最小值。
getMin()方法：返回 min_stack 栈顶即可。 min_stack 作用分析：

min_stack 等价于遍历 stack所有元素，把升序的数字都删除掉，留下一个从栈底到栈顶降序的栈。相当于给 stack 中的降序元素做了标记，每当 pop() 这些降序元素，min_stack 会将相应的栈顶元素 pop() 出去，保证其栈顶元素始终是 stack 中的最小元素。

复杂度分析：

时间复杂度 O(1) ：压栈，出栈，获取最小值的时间复杂度都为 O(1) 。空间复杂度 O(N) ：包含 N 个元素辅助栈占用线性大小的额外空间。

GIF图：https://pic.leetcode-cn.com/28724fa9f92b6952f7fdaf8760edd1dea850b137c22df28751f1cdd4d2680992-155.gif

最小栈法

javascript

class MinStack {
  constructor() {
    this.auxSt = []
    this.st = []
  }

  push(val) {
    this.st.push(val)
    if (this.auxSt.length === 0 || val <= this.auxSt[this.auxSt.length - 1]) {
      // 和要循环删除，保持单调性的逻辑不同（滑动窗口为了保证）
      this.auxSt.push(val)
    }
  }
  pop() {
    const p = this.st.pop()
    if (p === this.auxSt[this.auxSt.length - 1]) {
      this.auxSt.pop()
    }
  }
  top() {
    return this.st[this.st.length - 1]
  }
  getMin() {
    return this.auxSt[this.auxSt.length - 1]
  }
}