LeetCode-155最小栈

题目描述

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

提示：

• -231 <= val <= 231 - 1
• pop、top 和 getMin 操作总是在 非空栈 上调用
• push, pop, top, and getMin最多被调用 3 * 104 次

---

题解

方法一-辅助栈

利用一个辅助栈 min_stack 来存储当前栈中的最小值。每次 push 操作时，将当前值与 min_stack 栈顶的最小值比较，并将较小者压入 min_stack。这样，min_stack 的栈顶始终是当前栈中的最小值。

class MinStack(object):

    def __init__(self):
        self.stack = []
        self.min_stack = [2e31]
        

    def push(self, val):
        self.stack.append(val)
        self.min_stack.append(min(val, self.min_stack[-1]))
        

    def pop(self):
        self.stack.pop()
        self.min_stack.pop()

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

    def getMin(self):
        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()

复杂度分析

• 时间复杂度：push、pop、top 和 getMin 操作均为 O(1)。
• 空间复杂度：O(n)，需要额外的辅助栈存储最小值。

方法二-差值法

通过存储元素与当前最小值的差值，减少额外空间的使用，并在操作中动态维护最小值。

1. 差值存储：每个元素入栈时，存储其与当前最小值的差值（而不是实际值）。
2. 动态维护最小值：当遇到更小的元素时，更新最小值；当弹出导致最小值变化的元素时，逆向恢复之前的最小值。
3. 高效解码：在获取栈顶元素时，根据差值和当前最小值还原实际值。

class MinStack:
    def __init__(self):
        self.stack_diff = []  # 存储差值的栈
        self.mini = float('inf')  # 当前最小值

    def push(self, val: int) -> None:
        if not self.stack_diff:
            # 栈为空时，压入0，并初始化最小值
            self.stack_diff.append(0)
            self.mini = val
        else:
            # 计算当前值与当前最小值的差值，并压入栈
            diff = val - self.mini
            self.stack_diff.append(diff)
            # 若当前值更小，更新最小值
            if diff < 0:
                self.mini = val

    def pop(self) -> None:
        if not self.stack_diff:
            return
        diff = self.stack_diff.pop()
        if diff < 0:
            # 若差值为负，说明当前元素是最小值，弹出后需恢复之前的最小值
            self.mini -= diff  # 恢复公式：原最小值 = 当前最小值 - 差值

    def top(self) -> int:
        diff = self.stack_diff[-1]
        if diff >= 0:
            # 差值为正，说明当前元素入栈时未改变最小值，实际值为最小值 + 差值
            return self.mini + diff
        else:
            # 差值为负，说明当前元素是入栈时的最小值
            return self.mini

    def getMin(self) -> int:
        return self.mini

复杂度分析

• 时间复杂度：
  • push、pop、top、getMin 均为 O(1)，仅涉及常数次算术和栈操作。
• 空间复杂度：
  • O(n)，其中 n 为栈中元素数量。每个元素存储一个差值，最坏情况下与普通栈空间相同，但避免了显式存储冗余的最小值。

---