Min Stack（最小栈）

题目 / Problem

中文： 设计一个支持 push、pop、top 和在常数时间内获取最小元素的栈。

实现 MinStack 类：
Implement the MinStack class:

• MinStack()：初始化栈对象。
  Initializes the stack object.
• void push(int value)：将元素 value 压入栈中。
  Pushes value onto the stack.
• void pop()：移除栈顶元素。
  Removes the top element.
• int top()：返回栈顶元素。
  Returns the top element.
• int getMin()：返回栈中的最小元素。
  Returns the minimum element in the stack.

每个函数都必须具有 O(1) 时间复杂度。
Every function must run in O(1) time.

English: Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

示例 / Example

Input:
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output:
[null,null,null,null,-3,null,0,-2]

const minStack = new MinStack();

minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // -3
minStack.pop();
minStack.top();    // 0
minStack.getMin(); // -2

约束 / Constraints

• -2³¹ <= value <= 2³¹ - 1
• pop、top 和 getMin 总是在非空栈上调用。
  pop, top, and getMin are always called on a non-empty stack.
• 最多调用 push、pop、top 和 getMin 共 3 × 10⁴ 次。
  At most 3 × 10⁴ total calls will be made to push, pop, top, and getMin.

普通栈的问题 / Problem with an Ordinary Stack

普通栈可以在 O(1) 时间内完成 push、pop 和 top。但如果 getMin() 每次都遍历整个栈寻找最小值，它需要 O(n) 时间，不满足题目要求。
A normal stack performs push, pop, and top in O(1) time. But scanning the whole stack in every getMin() call takes O(n), violating the requirement.

为了让 getMin() 达到 O(1)，必须在元素入栈时提前保存最小值信息。
To make getMin() constant-time, store minimum information when each element is pushed.

解题思路：每个位置保存当前最小值 / Approach: Store the Current Minimum at Every Position

栈中的每个元素不只保存 value，还保存该元素入栈后整个栈的最小值 currentMin：
Each stack entry stores not only value, but also currentMin, the minimum of the entire stack after that value was pushed:

[value, currentMin]

压入新值时：
When pushing a new value:

currentMin = min(value, previousMin)

如果栈为空，新值本身就是当前最小值。
If the stack is empty, the new value is the current minimum.

这样：
This makes every operation simple:

• push：计算并保存新的当前最小值。
  push: calculate and store the new current minimum.
• pop：直接移除栈顶记录；下面一条记录已经保存了恢复后的最小值。
  pop: remove the top entry; the entry below already stores the restored minimum.
• top：读取栈顶记录的 value。
  top: read the top entry's value.
• getMin：读取栈顶记录的 currentMin。
  getMin: read the top entry's currentMin.

JavaScript 实现 / JavaScript Implementation

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

  /**
   * @param {number} value
   * @return {void}
   */
  push(value) {
    const currentMin = this.stack.length === 0
      ? value
      : Math.min(value, this.stack[this.stack.length - 1][1]);

    this.stack.push([value, currentMin]);
  }

  /**
   * @return {void}
   */
  pop() {
    this.stack.pop();
  }

  /**
   * @return {number}
   */
  top() {
    return this.stack[this.stack.length - 1][0];
  }

  /**
   * @return {number}
   */
  getMin() {
    return this.stack[this.stack.length - 1][1];
  }
}

题目保证 pop()、top() 和 getMin() 只会在非空栈上调用，因此这些方法不需要额外处理空栈。
The problem guarantees that pop(), top(), and getMin() are called only on non-empty stacks, so no additional empty-stack handling is required.

执行过程 / Walkthrough

执行示例操作：
Execute the example operations:

弹出 -3 后，无需重新扫描栈。新的栈顶记录 [0,-2] 已经保存了此时的最小值 -2。
After popping -3, no rescan is needed. The new top entry [0,-2] already stores the restored minimum -2.

为什么弹出后能恢复旧最小值？ / Why Is the Previous Minimum Restored After Pop?

每条记录保存的是“该记录位于栈顶时的最小值”。
Each entry stores the minimum for the exact stack state in which that entry is on top.

value  currentMin
-2     -2
 0     -2
-3     -3

弹出最上方记录后，下面的记录重新成为栈顶，它保存的 currentMin 自然就是恢复后的正确最小值。
After removing the top entry, the entry below becomes the new top, and its stored currentMin is exactly the restored minimum.

重复最小值 / Duplicate Minimum Values

该设计可以自然处理重复最小值：
This design naturally handles duplicate minima:

push(2) → [2, 2]
push(1) → [1, 1]
push(1) → [1, 1]

弹出一个 1 后，新的栈顶仍保存最小值 1。只有当两个 1 都被弹出后，最小值才恢复为 2。
After popping one 1, the new top still stores minimum 1. The minimum returns to 2 only after both copies are removed.

复杂度 / Complexity

• 空间复杂度：O(n)，每个栈元素保存一个值和一个对应的最小值。
  Space: O(n), because every stack entry stores one value and one associated minimum.

虽然每个元素保存两个数字，但常数倍不会改变渐进空间复杂度。
Each entry stores two numbers, but a constant factor does not change the asymptotic space complexity.

两个栈的解法 / Two-Stack Approach

也可以使用：
Another valid design uses:

• values 保存所有普通栈元素。
  values to store ordinary stack values.
• minimums 保存当前出现过的最小值。
  minimums to store active minimum values.

class MinStackTwoStacks {
  constructor() {
    this.values = [];
    this.minimums = [];
  }

  push(value) {
    this.values.push(value);

    if (
      this.minimums.length === 0 ||
      value <= this.minimums[this.minimums.length - 1]
    ) {
      this.minimums.push(value);
    }
  }

  pop() {
    const value = this.values.pop();

    if (value === this.minimums[this.minimums.length - 1]) {
      this.minimums.pop();
    }
  }

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

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

压入最小值栈时必须使用 value <= currentMin，不能只使用 <。等号用于保存重复最小值，确保弹出其中一个后仍能得到正确结果。
The condition must be value <= currentMin, not just <. Equality preserves duplicate minima so popping one copy does not lose the current minimum.

两个栈的方案同样让所有操作保持 O(1)，空间复杂度为 O(n)。
The two-stack design also keeps every operation at O(1) with O(n) space.

方案对比 / Approach Comparison

易错点 / Common Pitfalls

• getMin() 不能每次遍历整个栈，否则是 O(n)。
  getMin() must not scan the entire stack, which would take O(n).
• 弹出当前最小值后，必须能够恢复此前的最小值。
  Popping the current minimum must restore the previous minimum.
• 重复的最小值必须分别记录，不能只保存一个。
  Duplicate minimum values must be tracked separately.
• 两个栈的方案中，压入最小值栈的条件必须包含等号。
  In the two-stack design, the condition for pushing onto the minimum stack must include equality.
• top() 返回普通栈顶值，而 getMin() 返回当前最小值，两者不要混淆。
  top() returns the ordinary top value, while getMin() returns the current minimum.
• 题目要求每个操作都严格为 O(1)，不能依赖延迟扫描恢复最小值。
  Every operation must be strictly O(1); deferred rescanning is not allowed.