155. 最小栈

Origin: LeetCode 155

题目描述

设计一个支持 push、pop、top 操作，并能在 O(1) 时间检索到最小元素的栈。

接口

• MinStack() 初始化
• push(val) 将元素压入栈
• pop() 移除栈顶元素
• top() 获取栈顶元素
• getMin() 获取栈中最小元素（O(1)）

示例

MinStack minStack = new MinStack()
minStack.push(-2)
minStack.push(0)
minStack.push(-3)
minStack.getMin()   // 返回 -3
minStack.pop()
minStack.top()      // 返回 0
minStack.getMin()   // 返回 -2

约束

• -2^31 <= val <= 2^31 - 1
• pop、top、getMin 操作总是在非空栈上调用
• push、pop、top、getMin 的时间复杂度都是 O(1)

关键信息

• 你做过 HackerRank 第 41 题（双栈队列），栈操作很熟
• 关键：一个栈存数据，另一个栈存当前最小值
• getMin 直接读辅助栈栈顶，O(1)

Resolution

我的解法

class MinStack {
    stack: number[] = []
    minStack: number[] = []
 
    push(value: number): void {
        this.stack.push(value)
        const min = this.minStack[this.minStack.length - 1] ?? value
        if (this.minStack.length && value < min) {
            this.minStack.push(value)
        } else {
            this.minStack.push(min)
        }
    }
 
    pop(): void {
        this.stack.pop()
        this.minStack.pop()
    }
 
    top(): number {
        return this.stack[this.stack.length - 1]
    }
 
    getMin(): number {
        return this.minStack[this.minStack.length - 1]
    }
}

解题思路

双栈：stack 存数据，minStack 存当前最小值。

push 时：

• stack 正常 push
• minStack push 的是 min(当前值, minStack 栈顶)。如果 minStack 为空，push 当前值

pop 时两个栈同步 pop，保证 minStack 栈顶始终是当前 stack 的最小值。getMin 直接读 minStack 栈顶，O(1)。

复杂度

• push/pop/top/getMin：都是 O(1)
• 空间：O(n)，两个栈