LeetCode 栈结构经典题目解析与代码实现

栈（Stack）的逻辑核心是后进先出（LIFO, Last In First Out）。在处理具有'嵌套'、'匹配'或'寻找最近一个更大/更小'这类问题时，栈是非常强大的工具。

1. 有效的括号 (LeetCode 20)

核心思想：匹配消消乐。

• 直观思路：
  • 遍历字符串，遇到左括号 ([{ 就入栈。
  • 遇到右括号 )]}，就看栈顶是不是对应的左括号。
  • 如果是，就'抵消'（出栈）；如果不是或者栈空了，说明非法。
  • 最后如果栈空了，说明全部匹配成功。
• 复杂度： 时间 O(N)，空间 O(N)。

代码实现 (Python):

def isValid(s: str) -> bool:
    stack = []
    mapping = {")": "(", "]": "[", "}": "{"}
    for char in s:
        if char in mapping:
            top_element = stack.pop() if stack else '#'
            if mapping[char] != top_element:
                return False
        else:
            stack.append(char)
    return not stack

2. 最小栈 (LeetCode 155)

核心思想：同步辅助栈。

• 直观思路：
  • 普通的栈无法在 O(1) 时间内找到最小值，因为最小值可能被压在下面。
  • 解决： 准备一个辅助栈 min_stack，它和主栈同步。
  • 辅助栈的每个位置存：'主栈从底部到当前位置为止的最小值'。
  • 这样，无论主栈怎么弹出，辅助栈的顶部永远是当前剩下的数里的最小值。
• 复杂度： O(1) 时间完成所有操作。

代码实现 (Python):

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]

3. 字符串解码 (LeetCode 394)

核心思想：遇到 [ 压入现场，遇到 ] 恢复现场。

• 直观思路：
  • 比如 3[a2[c]]。我们需要处理嵌套。
  • 遇到数字：计算倍数。
  • 遇到字符：拼接到当前结果。
  • 遇到 [： 说明进入了内部层级。要把当前的字符串和当前的倍数一起压入栈中，然后重置它们，开始处理括号内部。
  • 遇到 ]： 说明内部层级结束。从栈里弹出'外层的字符串'和'倍数'，把当前内部的结果重复 N 次后接在外层字符串后面。
• 复杂度： 时间 O(S)，空间 O(S)（S 是解码后的长度）。

代码实现 (Python):

def decodeString(s: str) -> str:
    stack = []
    curr_str = ""
    curr_num = 0
    for char in s:
        if char.isdigit():
            curr_num = curr_num * 10 + int(char)
        elif char == '[':
            stack.append((curr_str, curr_num))
            curr_str, curr_num = "", 0
        elif char == ']':
            last_str, num = stack.pop()
            curr_str = last_str + num * curr_str
        else:
            curr_str += char
    return curr_str

4. 每日温度 (LeetCode 739)

核心思想：单调栈（Monotonic Stack）。

• 直观思路：
  • 我们要找'右边第一个比我大的数'。
  • 遍历数组，如果当前温度比栈顶的温度高，说明栈顶那些人在'等'的更高温终于来了！
  • 不断弹出栈顶，并计算天数差（当前索引 - 栈顶索引）。
  • 如果当前温度低，就入栈等待。
  • 栈内特点： 存的是下标，对应的温度从栈底到栈顶是递减的。
• 复杂度： 时间 O(N)（每个元素只进出栈一次）。

代码实现 (Python):

def dailyTemperatures(temperatures):
    n = len(temperatures)
    res = [0] * n
    stack = []
    for i in range(n):
        while stack and temperatures[i] > temperatures[stack[-1]]:
            prev_index = stack.pop()
            res[prev_index] = i - prev_index
        stack.append(i)
    return res

5. 柱状图中最大的矩形 (LeetCode 84)

核心思想：单调栈（找左右边界）。

• 直观思路：
  • 对于每一根柱子，以它的高度为矩形的高度，能向左右延伸多远？
  • 延伸的边界是：左右两边第一个比它矮的柱子。
  • 我们维护一个单调递增栈：
    1. 如果当前柱子比栈顶高，入栈。
    2. 如果当前柱子比栈顶矮，说明栈顶柱子的右边界找到了。
    3. 栈顶柱子弹出来，它左边的边界就是现在的栈顶。
  • 技巧： 在数组开头和结尾加一个高度为 0 的'哨兵'，确保所有柱子都能被计算。
• 复杂度： 时间 O(N)。

代码实现 (Python):

def largestRectangleArea(heights):
    heights = [0] + heights + [0]
    stack = []
    max_area = 0
    for i in range(len(heights)):
        while stack and heights[i] < heights[stack[-1]]:
            h = heights[stack.pop()]
            w = i - stack[-1] - 1
            max_area = max(max_area, h * w)
        stack.append(i)
    return max_area

刷题总结

1. 什么时候用栈？ 题目有'匹配'、'最近相关性'、'逆序输出'、'撤销操作'等关键词时。
2. 什么是单调栈？ 专门解决'寻找左/右边第一个比我大/小的元素'。
3. 下标 or 数值？ 在单调栈题目（如温度、矩形）中，通常栈里存的是下标，因为下标既能找到数值，又能计算距离。
4. 哨兵位： 像'矩形'这类题，加个 0 可以避免处理遍历完后栈内还有残留元素的情况，非常实用。