最小栈

实现一个栈，包含 push()、pop()、top() 和 getMin() 方法。 getMin() 方法返回栈中最小值，要求在常数时间内完成。

Code

class MinStack {
  // 辅助栈，单调递减，栈顶永远是最小值，最好情况下占用一个空间，最坏情况下占用 N 个空间
  monotoneStack = [];
  // 主栈
  stack = [];
  constructor() {}
  // 添加元素到栈中
  push(val) {
    // 这里要使用小于等于，否则主栈中存在多个最小值时，会被错误的弹出，导致结果错误
    if (this.stack.length === 0 || val <= this.monotoneStack[this.monotoneStack.length - 1]) {
      // 使辅助栈保持单调递减
      this.monotoneStack.push(val);
    }
    this.stack.push(val);
  }
  // 弹出栈顶元素
  pop() {
    // 如果主栈中弹出的元素是最小元素，那么辅助栈也要一起弹出。
    // 需要注意的是：最小元素可能是多个，因此 push 时使用 <=。
    const item = this.stack.pop();
    if (item !== undefined && item === this.monotoneStack[this.monotoneStack.length - 1]) {
      this.monotoneStack.pop();
    }
  }
  // 查看栈顶元素
  top() {
    return this.stack[this.stack.length - 1];
  }
  // 查看栈中最小值
  getMin() {
    return this.monotoneStack[this.monotoneStack.length - 1];
  }
}