Medium

题目描述

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

实现 MinStack 类:

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

你必须实现 O(1) 时间复杂度的每个函数。

示例 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 次

解题思路

这道题的关键在于如何在 O(1) 时间内获取栈中的最小元素。有两种经典的解法：

方法一：辅助栈 使用一个主栈存储所有元素，另外用一个辅助栈专门存储最小值。当 push 元素时，主栈正常添加元素；辅助栈只在新元素小于等于当前最小值时才添加。当 pop 元素时，如果弹出的元素等于当前最小值，辅助栈也要弹出一个元素。

方法二：单栈存储差值 使用一个栈存储当前元素与当前最小值的差值，同时维护一个变量记录当前最小值。这种方法更节省空间，但实现稍复杂。

推荐方法一，因为思路更清晰，实现更简单，且空间复杂度在实际应用中是可接受的。核心思想是用空间换时间，通过维护额外的最小值栈来确保 getMin 操作的 O(1) 时间复杂度。

代码实现

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

class MinStack:

    def __init__(self):
        self.stk = []
        self.min_stk = []

    def push(self, val: int) -> None:
        self.stk.append(val)
        if not self.min_stk or val <= self.min_stk[-1]:
            self.min_stk.append(val)

    def pop(self) -> None:
        if self.stk[-1] == self.min_stk[-1]:
            self.min_stk.pop()
        self.stk.pop()

    def top(self) -> int:
        return self.stk[-1]

    def getMin(self) -> int:
        return self.min_stk[-1]

public class MinStack {
    private Stack<int> stk;
    private Stack<int> minStk;

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

var MinStack = function() {
    this.stack = [];
    this.minStack = [];
};

MinStack.prototype.push = function(val) {
    this.stack.push(val);
    if (this.minStack.length === 0 || val <= this.minStack[this.minStack.length - 1]) {
        this.minStack.push(val);
    }
};

MinStack.prototype.pop = function() {
    const popped = this.stack.pop();
    if (popped === this.minStack[this.minStack.length - 1]) {
        this.minStack.pop();
    }
};

MinStack.prototype.top = function() {
    return this.stack[this.stack.length - 1];
};

MinStack.prototype.getMin = function() {
    return this.minStack[this.minStack.length - 1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
pushO(1)O(1)
popO(1)O(1)
topO(1)O(1)
getMinO(1)O(1)
整体空间复杂度-O(n)

其中 n 为栈中元素的个数。辅助栈在最坏情况下（元素递减序列）会存储所有元素，因此整体空间复杂度为 O(n)。

相关题目