包含最小值的栈

问题

设计一个栈，除了支持 push、pop、top 操作外，还能在 O(1) 时间内获取栈中的最小元素。

解答

思路

使用辅助栈同步记录每个状态下的最小值。每次 push 时，辅助栈存入当前最小值；pop 时两个栈同步弹出。

实现

class MinStack {
  constructor() {
    this.stack = []    // 数据栈
    this.minStack = [] // 辅助栈，存储对应位置的最小值
  }

  // 入栈
  push(val) {
    this.stack.push(val)
    // 辅助栈为空或新值更小，则存入新值；否则存入当前最小值
    if (this.minStack.length === 0) {
      this.minStack.push(val)
    } else {
      this.minStack.push(Math.min(val, this.getMin()))
    }
  }

  // 出栈
  pop() {
    this.stack.pop()
    this.minStack.pop()
  }

  // 获取栈顶元素
  top() {
    return this.stack[this.stack.length - 1]
  }

  // 获取最小值
  getMin() {
    return this.minStack[this.minStack.length - 1]
  }
}

测试

const stack = new MinStack()
stack.push(3)
stack.push(2)
stack.push(5)
console.log(stack.getMin()) // 2
stack.pop()
console.log(stack.getMin()) // 2
stack.pop()
console.log(stack.getMin()) // 3

优化：减少辅助栈空间

当新元素大于当前最小值时，辅助栈不入栈：

class MinStack {
  constructor() {
    this.stack = []
    this.minStack = []
  }

  push(val) {
    this.stack.push(val)
    // 只有小于等于当前最小值时才入辅助栈
    if (this.minStack.length === 0 || val <= this.getMin()) {
      this.minStack.push(val)
    }
  }

  pop() {
    // 弹出值等于最小值时，辅助栈也弹出
    if (this.stack.pop() === this.getMin()) {
      this.minStack.pop()
    }
  }

  top() {
    return this.stack[this.stack.length - 1]
  }

  getMin() {
    return this.minStack[this.minStack.length - 1]
  }
}

关键点

• 辅助栈与数据栈同步操作，记录每个状态的最小值
• 所有操作时间复杂度均为 O(1)
• 优化版本：只在新值 ≤ 当前最小值时才入辅助栈，节省空间
• 注意边界：辅助栈判断用 <= 而非 <，处理重复最小值的情况