9. Min-Tracking Stack Implementation

Origin: Min-Tracking Stack Implementation

Implement a stack that supports push, pop, top, and getMin operations in O(1) time, where getMin returns the minimum element.

Example

Input

n = 10
operations = ['push 2', 'push 0', 'push 3', 'push 0', 'getMin', 'pop', 'getMin', 'pop', 'top', 'getMin']

Output

[0,0,0,0]

Explanation

- push 2 → stack = [2], min = 2 2. 
- push 0 → stack = [2,0], min = 0 3.
- push 3 → stack = [2,0,3], min = 0 4. 
- push 0 → stack = [2,0,3,0], min = 0 5. 
- getMin → returns 0 6. 
- pop → removes 0, stack = [2,0,3], min = 0 7. 
- getMin → returns 0 8. 
- pop → removes 3, stack = [2,0], min = 0 9. 
- top → returns 0 10. getMin → returns 0

Input Format

• operations: array of n number of operations, each matching exactly one of:
  • “push x” where x is an integer and 0 <= x <= 100
  • “pop”
  • “top”
  • “getMin”
• The next n lines contain the value of elements in the array.
• At any point in the sequence, the number of “pop” operations performed so far must be strictly less than the number of preceding “push” operations (so that the stack is never empty when “pop”, “top”, or “getMin” is called).

Constraints

• For each “push x” operation, 0 <= x <= 100 and x is an integer
• Each entry in operations must match the pattern ^(push \d+|pop|top|getMin)$
• pop, top, and getMin operations are only invoked when the stack is non-empty
• Total number of push operations <= n where n is the length of operations array

Output Format

• An integer array of length equal to the total number of “top” and “getMin” operations in the input

Sample Input 0

2
push 5
getMin

Sample Output 0

5

Sample Input 1

2
push 0
top

Sample Output 1

0

Resolution

核心思路：辅助栈（双栈法）

题目要求 O(1) 的 getMin。如果每次 getMin 都遍历整个栈，复杂度是 O(n)，不达标。

解法是维护两个栈：

1. 数据栈：正常存数据。
2. 最小值栈：栈顶始终是当前数据栈中的最小值。

• push 时：如果新值 <= 最小值栈栈顶，就同时压入最小值栈。
• pop 时：如果弹出的值 == 最小值栈栈顶，最小值栈也弹出。
• getMin：直接读最小值栈栈顶，O(1)。

关键细节：用 <= 不用 <

题目中有多个相同值（比如多个 0）。如果 push 时用 <，第二个 0 不会进最小值栈。当第一个 0 被 pop 时，最小值栈提前弹出，后续 getMin 就错了。用 <= 保证每个最小值都有对应的最小值栈条目。

踩坑经历

第一版解法直接用 Math.min(...stack) 遍历整个数组，能 AC 但不是题目要求的 O(1)。Math.min(...stack) 展开了整个数组，每次 getMin 都做一次线性扫描。如果 n 次操作全是 getMin，总复杂度 O(n²)。

我的解法（O(n) 版，能 AC 但不满足题目要求）

function processCouponStackOperations(operations: string[]): number[] {
    const stack: number[] = []
    const result: number[] = []
    operations.forEach((op) => {
        const [o, str] = op.split(' ')
        switch (o) {
            case 'push':
                stack.push(Number(str))
                break
            case 'pop':
                stack.pop()
                break
            case 'getMin':
                let min = Math.min(...stack)
                result.push(min)
                break
            case 'top':
                result.push(Number(stack[stack.length - 1]))
                break
            default:
                break
        }
    })
    return result
}

最优解法（O(1) 版，双栈法）

function processCouponStackOperations(operations: string[]): number[] {
    const stack: number[] = []
    const minStack: number[] = []
    const result: number[] = []
 
    operations.forEach((op) => {
        const [o, str] = op.split(' ')
        switch (o) {
            case 'push': {
                const val = Number(str)
                stack.push(val)
                if (minStack.length === 0 || val <= minStack[minStack.length - 1]) {
                    minStack.push(val)
                }
                break
            }
            case 'pop': {
                const popped = stack.pop()
                if (popped === minStack[minStack.length - 1]) {
                    minStack.pop()
                }
                break
            }
            case 'getMin':
                result.push(minStack[minStack.length - 1])
                break
            case 'top':
                result.push(stack[stack.length - 1])
                break
        }
    })
    return result
}

复杂度：

• 时间：O(n)，每个操作都是 O(1)。
• 空间：O(n)，最坏情况（递减序列）最小值栈和数据栈等大。

同类题：LeetCode 155. 最小栈。经典面试题，高频考点。