155.最小栈

题目描述

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

示例

示例 1：

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

示例 2：

输入：
["MinStack","push","push","getMin","pop","getMin"]
[[],[0],[1],[],[],[]]

输出：
[null,null,null,0,null,0]

提示

• -2^31 <= val <= 2^31 - 1
• pop、top 和 getMin 操作总是在 非空栈 上调用
• push, pop, top 和 getMin 的操作次数最多 3 * 10^4 次

解题思路

• 使用双栈方法实现最小栈
• 主栈正常存储所有元素
• 辅助最小栈同步记录当前状态的最小值
• 每次 push 操作时，同时维护最小栈的状态
• 确保 getMin() 方法能在 O(1) 时间内返回最小元素

Swift 代码实现

class MinStack {
    // 主栈，存储所有元素
    private var stack: [Int]
    // 最小栈，同步记录最小元素
    private var minStack: [Int]

    // 初始化方法
    init() {
        stack = []
        minStack = []
    }
    
    // 入栈操作
    func push(_ val: Int) {
        // 主栈正常添加元素
        stack.append(val)
        
        // 最小栈维护最小值
        if minStack.isEmpty || val <= minStack.last! {
            minStack.append(val)
        }
    }
    
    // 出栈操作
    func pop() {
        // 如果出栈元素是当前最小值，最小栈也需要同步出栈
        if let top = stack.last, top == minStack.last {
            minStack.removeLast()
        }
        
        // 主栈出栈
        stack.removeLast()
    }
    
    // 获取栈顶元素
    func top() -> Int {
        return stack.last!
    }
    
    // 获取最小元素
    func getMin() -> Int {
        return minStack.last!
    }
}

代码解释：

1. 定义两个数组：stack（主栈）和 minStack（最小栈）
2. push 方法：
   • 将元素压入主栈
   • 如果最小栈为空或新元素小于等于当前最小值，压入最小栈
3. pop 方法：
   • 如果出栈元素等于最小栈栈顶，同时弹出最小栈
   • 弹出主栈元素
4. top 方法：返回主栈栈顶元素
5. getMin 方法：返回最小栈栈顶元素（即当前最小值）

复杂度分析

• 时间复杂度：O(1)，所有操作都是常数时间
• 空间复杂度：O(n)，需要额外的最小栈存储空间，最坏情况下空间与元素数量成正比

额外说明：

• 这是一种用空间换时间的经典设计模式
• 通过额外的最小栈，实现了 O(1) 获取最小元素
• 适用于需要频繁获取最小元素的场景
• 算法核心在于同步维护最小栈的状态

算法对比

1. 单栈实现：需要遍历整个栈，时间复杂度 O(n)
2. 本解法（双栈）：始终保持 O(1) 时间复杂度
3. 适用性：数据量较大时，本解法性能更优