最小栈

难度: Medium

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

Submission

运行时间: 34 ms

内存: 19.4 MB

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:
            self.min_stack.append(val)
        else:
            if 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()
        return self.stack.pop()


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


    def getMin(self) -> int:
        return self.min_stack[-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()

Explain

该题解使用两个栈来实现最小栈，一个栈 stack 存储所有元素，另一个栈 min_stack 存储当前的最小元素。在 push 操作时，如果新元素小于等于 min_stack 的栈顶元素，就将新元素也压入 min_stack。在 pop 操作时，如果弹出的元素等于 min_stack 的栈顶元素，就将 min_stack 的栈顶元素也弹出。这样可以保证 min_stack 的栈顶元素始终是当前 stack 中的最小元素。

时间复杂度: O(1)

空间复杂度: O(n)

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:
            self.min_stack.append(val)
        else:
            if val <= self.min_stack[-1]:
                self.min_stack.append(val)  # 如果新元素小于等于当前最小元素，将新元素压入 min_stack


    def pop(self) -> None:
        if self.stack[-1] == self.min_stack[-1]:
            self.min_stack.pop()  # 如果弹出的元素是当前最小元素，也将其从 min_stack 中弹出
        return self.stack.pop()


    def top(self) -> int:
        return self.stack[-1]  # 返回栈顶元素


    def getMin(self) -> int:
        return self.min_stack[-1]  # 返回 min_stack 的栈顶元素，即当前最小元素

Explore

使用两个栈来实现最小栈的主要优点是其简洁性和效率。使用两个栈可以在常数时间内完成所有操作，包括插入、删除和获取最小元素。如果使用哈希表，虽然可以快速访问元素，但不易于维护每个元素的最小值状态。使用优先队列（如最小堆）虽然可以快速获取最小值，但在删除非堆顶元素时效率较低，不适合本问题的需求，因为栈的元素删除顺序是后进先出，这与最小堆的操作不兼容。因此，使用两个栈是一种既简单又高效的设计策略。

这是因为`min_stack`的栈顶元素表示的是在主栈`stack`中所有元素的当前最小值。当`pop`操作发生时，如果弹出的元素等于`min_stack`的栈顶元素，这意味着栈中的最小元素被移除了。因此，为了维护`min_stack`的正确性，表示当前最小值的元素也必须从`min_stack`中移除。这样可以确保`min_stack`的栈顶元素始终是剩余元素中的最小值。

在`push`操作中，如果新压入的元素大于`min_stack`的栈顶元素，这意味着新元素对当前的最小元素没有影响，因为`min_stack`的栈顶元素已经是小于或等于新元素的最小值。将大于当前最小值的元素添加到`min_stack`中将无助于维护最小值状态，并且会增加不必要的空间占用。因此，只有当新元素小于或等于`min_stack`的栈顶元素时，才将其加入`min_stack`，以更新当前的最小值。

`getMin`操作返回`min_stack`的栈顶元素能保证是当前栈中的最小元素，因为`min_stack`是专门设计来在每个时刻存储`stack`中所有元素的最小值的。每次新元素入栈时，如果该元素小于或等于`min_stack`的栈顶元素，它就被加入`min_stack`。这样，无论何时，`min_stack`的栈顶元素都是`stack`中当前所有元素的最小值。因此，`getMin`操作直接返回`min_stack`的栈顶元素即可得到当前的最小值。