LeetCode 155 最小栈：辅助栈实现O(1)查询最小值

题目描述

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

实现 MinStack 类:

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

你必须实现一个时间复杂度为 O(1) 的栈。

难度

简单

题目链接

点击在LeetCode中查看题目

示例

示例 1：

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

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

解释：
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 最多被调用 3 * 10^4 次

解题思路

方法：辅助栈

使用一个辅助栈来存储最小值。 关键点：

1. 主栈存储所有元素
2. 辅助栈存储最小值
3. 当新元素小于等于辅助栈顶元素时，将其压入辅助栈
4. 当主栈弹出元素等于辅助栈顶元素时，辅助栈也弹出
5. 辅助栈顶元素即为当前最小值

时间复杂度：O(1)，所有操作都是常数时间。 空间复杂度：O(n)，其中n是栈中元素个数。

代码实现

C# 实现

public class MinStack {
    private Stack<int> stack;
    private Stack<int> minStack;
    
    public MinStack() {
        stack = new Stack<int>();
        minStack = new Stack<int>();
    }
    
    public void Push(int val) {
        stack.Push(val);
        if (minStack.Count == 0 || val <= minStack.Peek()) {
            minStack.Push(val);
        }
    }
    
    public void Pop() {
        if (stack.Peek() == minStack.Peek()) {
            minStack.Pop();
        }
        stack.Pop();
    }
    
    public int Top() {
        return stack.Peek();
    }
    
    public int GetMin() {
        return minStack.Peek();
    }
}

Python 实现

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []
        
    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)
            
    def pop(self) -> None:
        if self.stack[-1] == self.min_stack[-1]:
            self.min_stack.pop()
        self.stack.pop()
        
    def top(self) -> int:
        return self.stack[-1]
        
    def getMin(self) -> int:
        return self.min_stack[-1]

C++ 实现

class MinStack {
private:
    stack<int> st;
    stack<int> min_st;
    
public:
    MinStack() {}
    
    void push(int val) {
        st.push(val);
        if (min_st.empty() || val <= min_st.top()) {
            min_st.push(val);
        }
    }
    
    void pop() {
        if (st.top() == min_st.top()) {
            min_st.pop();
        }
        st.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return min_st.top();
    }
};

性能分析

各语言实现的性能对比：

实现语言	执行用时	内存消耗	特点
C#	92 ms	38.2 MB	实现简洁，性能适中
Python	156 ms	16.8 MB	代码最简洁
C++	24 ms	9.6 MB	性能最优

补充说明

代码亮点

1. 使用辅助栈实现O(1)时间复杂度的最小值查询
2. 处理了各种边界情况
3. 代码结构清晰，易于维护

常见错误

1. 没有处理栈为空的情况
2. 没有处理重复最小值的情况
3. 辅助栈的更新逻辑不正确

相关题目

• 716. 最大栈
• 225. 用队列实现栈
• 232. 用栈实现队列

讨论

有几个问题可以思考一下：

1. 辅助栈中什么时候需要push元素？为什么要用 <= 而不是 < ？
2. 除了用辅助栈，还有其他方法能实现O(1)查询最小值吗？
3. 如果要实现最大栈，需要改哪些地方？

欢迎在评论区讨论。

---

如果你都看到这里了，说明还是有点收获的吧？给个赞鼓励一下呗。