What is the main challenge in solving the Min Stack problem?

The main challenge is ensuring that all operations—push, pop, top, and getMin—run in constant time, O(1), while maintaining correct tracking of the minimum value.

How can we efficiently track the minimum element in a stack?

You can use a secondary stack to track the minimum value. Every time a new value is pushed, compare it with the current minimum and store the smaller of the two in the secondary stack.

What is the time complexity of the Min Stack problem?

The time complexity for each operation (push, pop, top, getMin) is O(1), making the solution highly efficient.

Can the Min Stack problem be solved with just one stack?

While it's possible, using two stacks is the most straightforward and efficient approach to ensure constant-time operations for both min tracking and stack management.

How do you handle edge cases like empty stacks in the Min Stack problem?

Edge cases, such as popping from an empty stack or calling getMin on an empty stack, are managed by checking if the stack is empty before performing operations.

#155

Medium

auto_awesome栈·状态

LeetCode 题解工作台

最小栈

设计一个支持 push ， pop ， top 操作，并能在常数时间内检索到最小元素的栈。实现 MinStack 类: MinStack() 初始化堆栈对象。 void push(int val) 将元素val推入堆栈。 void pop() 删除堆栈顶部的元素。 int top() 获取堆栈顶部…

栈设计

题目描述

设计一个支持 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]

解释：
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³¹ <= val <= 2³¹ - 1
pop、top 和 getMin 操作总是在 非空栈 上调用
push, pop, top, and getMin最多被调用 3 * 10⁴ 次

lightbulb

解题思路

方法一：双栈

我们用两个栈来实现，其中 stk1 用来存储数据，stk2 用来存储当前栈中的最小值。初始时，stk2 中存储一个极大值。

当我们向栈中压入一个元素 $x$ 时，我们将 $x$ 压入 stk1，并将 min(x, stk2[-1]) 压入 stk2。
当我们从栈中弹出一个元素时，我们将 stk1 和 stk2 的栈顶元素都弹出。
当我们要获取当前栈中的栈顶元素时，我们只需要返回 stk1 的栈顶元素即可。
当我们要获取当前栈中的最小值时，我们只需要返回 stk2 的栈顶元素即可。

每个操作的时间复杂度为 $O(1)$ 。整体的空间复杂度为 $O(n)$ ，其中 $n$ 为栈中元素的个数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

class MinStack:
    def __init__(self):
        self.stk1 = []
        self.stk2 = [inf]

    def push(self, val: int) -> None:
        self.stk1.append(val)
        self.stk2.append(min(val, self.stk2[-1]))

    def pop(self) -> None:
        self.stk1.pop()
        self.stk2.pop()

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

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


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Looking for efficient O(1) time complexity for all operations.
question_mark
Check if the candidate handles the edge cases when the stack becomes empty.
question_mark
Evaluate if the solution maintains stack synchronization properly, particularly with respect to the minimum tracking.

warning

常见陷阱

外企场景

error
Incorrect handling of stack underflow, especially for pop and getMin operations.
error
Failure to maintain the correct minimum values when elements are popped.
error
Confusion about how to manage two stacks or how to update the minimum value stack.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Implementing a stack that supports additional operations like peek.
arrow_right_alt
Designing a thread-safe version of the MinStack for concurrent operations.
arrow_right_alt
Optimizing space by reducing auxiliary stack usage while maintaining O(1) time complexity.

help

常见问题

外企场景

继续练习

#173 二叉搜索树迭代器 #225 用队列实现栈 #232 用栈实现队列