LeetCode怎样实现包含min函数的栈

引言

在数据结构与算法的学习过程中，栈(Stack)是一种非常重要的基础数据结构。栈遵循”后进先出”(LIFO)的原则，具有push(压栈)和pop(弹栈)等基本操作。在实际应用中，我们常常需要对栈进行扩展，添加一些额外的功能。

LeetCode上有一道经典的题目”155. 最小栈”(Min Stack)，要求设计一个栈，除了支持常规的栈操作外，还能在常数时间内检索到栈中的最小元素。本文将详细探讨如何实现这样一个包含min函数的栈。

问题描述

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

• push(x) —— 将元素 x 推入栈中。
• pop() —— 删除栈顶的元素。
• top() —— 获取栈顶元素。
• getMin() —— 检索栈中的最小元素。

示例：

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

基本思路分析

要实现一个能在O(1)时间内返回最小值的栈，关键在于如何维护当前栈中的最小值信息。如果只是简单地遍历栈来查找最小值，时间复杂度会是O(n)，这不符合题目要求。

我们需要设计一种数据结构，能够在每次push和pop操作时，都能同步更新当前的最小值信息。以下是几种常见的实现方法：

方法一：辅助栈法

这是最直观和常用的方法。我们使用两个栈： 1. 主栈：用于存储所有元素 2. 辅助栈：用于存储每个状态下的最小值

操作原理： - 当push一个新元素时： - 主栈正常push - 如果辅助栈为空或新元素 ≤ 辅助栈栈顶元素，则辅助栈也push这个新元素 - 否则，辅助栈再次push当前最小值(即辅助栈栈顶元素)

• 当pop时：

  • 主栈和辅助栈同时pop

• 当getMin时：

  • 直接返回辅助栈的栈顶元素

这种方法保证了辅助栈的栈顶始终是当前栈中的最小值，且所有操作的时间复杂度都是O(1)。

方法二：存储差值法

这种方法更节省空间，但实现起来稍复杂。基本思想是： - 栈中不直接存储元素值，而是存储当前元素与当前最小值的差值 - 使用一个变量min_val记录当前最小值

操作原理： - push(x): - 如果栈为空，min_val = x，压入0 - 否则，压入x - min_val，如果x < min_val，则更新min_val = x

• pop():

  • 弹出栈顶元素diff
  • 如果diff < 0，说明弹出的是最小值，需要更新min_val = min_val - diff
  • 否则，正常弹出

• top():

  • 查看栈顶diff
  • 如果diff < 0，说明当前栈顶是最小值，返回min_val
  • 否则，返回min_val + diff

• getMin():

  • 直接返回min_val

这种方法只需要一个栈和一个额外变量，空间复杂度更优。

代码实现

辅助栈法实现

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 or val <= self.min_stack[-1]:
            self.min_stack.append(val)
        else:
            self.min_stack.append(self.min_stack[-1])

    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()

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

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

存储差值法实现

class MinStack:

    def __init__(self):
        self.stack = []
        self.min_val = float('inf')

    def push(self, val: int) -> None:
        if not self.stack:
            self.min_val = val
            self.stack.append(0)
        else:
            diff = val - self.min_val
            self.stack.append(diff)
            if diff < 0:
                self.min_val = val

    def pop(self) -> None:
        diff = self.stack.pop()
        if diff < 0:
            self.min_val = self.min_val - diff

    def top(self) -> int:
        diff = self.stack[-1]
        if diff < 0:
            return self.min_val
        else:
            return self.min_val + diff

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

复杂度分析

辅助栈法

• 时间复杂度：所有操作都是O(1)
• 空间复杂度：O(n)，需要额外的辅助栈

存储差值法

• 时间复杂度：所有操作都是O(1)
• 空间复杂度：O(1)，只需要一个额外变量

边界条件与测试用例

在实现时需要考虑以下边界条件： 1. 空栈时调用pop、top或getMin 2. 连续push相同最小值 3. push和pop交替进行

测试用例示例：

def test_min_stack():
    # 测试辅助栈法
    minStack = MinStack()
    minStack.push(-2)
    minStack.push(0)
    minStack.push(-3)
    assert minStack.getMin() == -3
    minStack.pop()
    assert minStack.top() == 0
    assert minStack.getMin() == -2
    
    # 测试存储差值法
    minStack2 = MinStack()
    minStack2.push(2)
    minStack2.push(0)
    minStack2.push(3)
    minStack2.push(0)
    assert minStack2.getMin() == 0
    minStack2.pop()
    assert minStack2.getMin() == 0
    minStack2.pop()
    assert minStack2.getMin() == 0
    minStack2.pop()
    assert minStack2.getMin() == 2

实际应用场景

这种带有min功能的栈在实际中有多种应用： 1. 实现带有撤销功能的应用时，可能需要快速获取历史记录中的某些极值 2. 在图形处理软件中，可能需要跟踪一系列操作中的最小/最大值 3. 在算法设计中，如滑动窗口问题、单调栈问题等

总结

实现包含min函数的栈是一个经典的面试问题，考察了对栈数据结构的理解以及如何在基本数据结构上添加额外功能的能力。本文介绍了两种主要的实现方法：

1. 辅助栈法：直观易懂，实现简单，但需要额外的空间
2. 存储差值法：空间效率更高，但实现稍复杂

在实际应用中，可以根据具体场景选择合适的方法。如果空间不是主要考虑因素，辅助栈法是更优的选择；如果需要极致优化空间，则可以考虑存储差值法。

理解这类问题的关键在于分析如何在基本操作(push/pop)的同时维护额外的信息(最小值)，这也是许多算法问题中常见的技巧。通过这道题目，我们可以学习到如何在不影响原有数据结构性能的前提下，扩展其功能。