最小栈

难度: Easy

请你设计一个 最小栈 。它提供 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],[2],[-3],[],[],[],[]]

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

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(2);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 2.
minStack.getMin();   --> 返回 -2.

提示：

-2³¹ <= val <= 2³¹ - 1
pop、top 和 getMin 操作总是在 非空栈 上调用
push、pop、top 和 getMin 最多被调用 3 * 10⁴ 次

注意：本题与主站 155 题相同：https://leetcode-cn.com/problems/min-stack/

Submission

运行时间: 60 ms

内存: 17.9 MB

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.main_stack = list()
        self.support_stack = list()

    def push(self, x: int) -> None:
        self.main_stack.append(x)
        if len(self.support_stack) == 0 or x <= self.support_stack[-1]:
            self.support_stack.append(x)

    def pop(self) -> None:
        if self.main_stack.pop() == self.support_stack[-1]:
            self.support_stack.pop()

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

    def min(self) -> int:
        return self.support_stack[-1]



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

Explain

本题解的思路是使用两个栈，一个主栈 main_stack 用来实现正常的栈操作，另一个辅助栈 support_stack 用来存储当前栈中的最小元素。每次进行 push 操作时，如果新元素小于等于辅助栈的栈顶元素，或者辅助栈为空，则将新元素也压入辅助栈。进行 pop 操作时，如果主栈弹出的元素等于辅助栈的栈顶元素，则辅助栈也弹出一个元素。这样，辅助栈的栈顶元素始终是当前栈中的最小元素。

时间复杂度: O(1)

空间复杂度: O(n)

class MinStack:

    def __init__(self):
        \"\"\"
        initialize your data structure here.
        \"\"\"
        self.main_stack = list()  # 主栈
        self.support_stack = list()  # 辅助栈

    def push(self, x: int) -> None:
        self.main_stack.append(x)  # 压入主栈
        if len(self.support_stack) == 0 or x <= self.support_stack[-1]:
            self.support_stack.append(x)  # 如果新元素小于等于辅助栈栈顶，也压入辅助栈

    def pop(self) -> None:
        if self.main_stack.pop() == self.support_stack[-1]:
            self.support_stack.pop()  # 如果弹出的元素等于辅助栈栈顶，辅助栈也弹出

    def top(self) -> int:
        return self.main_stack[-1]  # 返回主栈栈顶

    def min(self) -> int:
        return self.support_stack[-1]  # 返回辅助栈栈顶，即最小元素


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

Explore

在实现最小栈时，使用两个栈的主要原因是简化实现和操作。虽然平衡树或堆可以在一般情况下提供对最小元素的快速访问，但它们的实现相对复杂，且在执行基本的栈操作（如压入、弹出）时可能不如使用两个栈那样直接和高效。使用两个栈可以确保所有操作（push、pop、min 和 top）的时间复杂度为 O(1)，这是因为所有操作都仅涉及对栈的基本操作，如压入和弹出，无需额外的结构调整。

当主栈中的元素被弹出时，辅助栈通过与主栈同步操作来确保其始终包含当前最小元素。具体的逻辑是：在执行 pop 操作时，会检查弹出的元素是否等于辅助栈的栈顶元素。如果等于，这意味着被弹出的元素是当前的最小值，因此辅助栈也需要弹出其栈顶元素以更新其最小值记录。这样，辅助栈的栈顶始终表示主栈中所有剩余元素的最小值。

在辅助栈中处理多个相同的最小值时，每次遇到一个新的最小值（或等于当前最小值的值），都会将这个值压入辅助栈，即使它与辅助栈的当前栈顶元素相同。这样做的目的是确保在主栈中每个相应的元素弹出时，辅助栈能够正确地同步弹出，从而维护准确的最小值记录。因此，如果连续压入多个相同的最小值，辅助栈会有多个相同的元素；当这些元素逐个从主栈中弹出时，辅助栈也会相应地逐个弹出这些最小值，直到发现新的最小值或所有元素被弹出。