跳到主要内容

栈的设计问题

如何让栈在 O(1) 内返回最小值？​

  • 问题 (155): 只用主栈时求最小值必须遍历, 因为不知道最小值何时被弹出;
  • 做法: 增加一个辅助栈 min, 与主栈同高, 第 i 项存"前 i 个元素的最小值";
  • 入栈: min.push(Math.min(min.at(-1), val));
  • 出栈: 两个栈同步 pop;
  • 初始化: min = [Infinity] 省去空栈特判;
class MinStack {
  stack = [];
  min = [Infinity];

  push(val) {
    this.stack.push(val);
    this.min.push(Math.min(this.min.at(-1), val));
  }

  pop() {
    this.stack.pop();
    this.min.pop();
  }

  top() {
    return this.stack.at(-1);
  }

  getMin() {
    return this.min.at(-1);
  }
}

如何用两个栈实现队列？​

  • 难点: 栈是后进先出, 队列要求先进先出;
  • 做法 (232): in 负责入队, out 负责出队;
  • 关键操作: 需要出队时, 把 in 全部弹出并压入 out, 两次逆序后顺序恢复为先进先出;
  • 分摊: 每个元素最多被搬运一次, 因此 pop 分摊 O(1)O(1);
class MyQueue {
  in = [];
  out = [];

  push(x) {
    this.in.push(x);
  }

  #shift() {
    if (this.out.length === 0) {
      while (this.in.length > 0) this.out.push(this.in.pop());
    }
  }

  pop() {
    this.#shift();
    return this.out.pop();
  }

  peek() {
    this.#shift();
    return this.out.at(-1);
  }

  empty() {
    return this.in.length === 0 && this.out.length === 0;
  }
}