栈结构在算法中的应用与LeetCode经典题解-平芜编程栈

1. 栈结构在算法中的核心价值

栈（Stack）作为计算机科学中最基础的数据结构之一，其"后进先出"（LIFO）的特性在算法设计中具有不可替代的作用。在实际工程和算法面试中，栈相关题目出现频率极高，LeetCode热题100中栈相关题目就占据了重要位置。掌握栈的精髓不仅能帮助我们高效解决特定类型问题，更能培养我们抽象问题本质的思维能力。

我刷题过程中发现，栈结构特别适合处理具有"最近相关性"的问题。比如括号匹配需要检查最近的开放括号，温度升高需要回溯最近的低温日期，这些场景下栈的LIFO特性都能完美匹配问题需求。接下来我将通过5道经典题目，拆解栈的不同应用范式。

2. 有效的括号（LeetCode 20）

2.1 问题本质与栈的适配性

给定一个只包含 '(', ')', '{', '}', '[' 和 ']' 的字符串，判断字符串是否有效。有效需满足：

左括号必须用相同类型的右括号闭合
左括号必须以正确的顺序闭合

这个问题的核心在于"最近打开的括号必须最先闭合"，这与栈的LIFO特性完全吻合。我们可以遍历字符串，遇到左括号就压栈，遇到右括号就检查栈顶是否匹配。

2.2 实现细节与边界处理

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

关键点：

使用字典存储括号映射关系，代码更简洁
遇到右括号时需要检查栈是否为空（比如输入为"]"的情况）
最终需要检查栈是否为空（比如输入为"["的情况）

实际编码时最容易忽略的是右括号出现在首位的情况，这时直接pop会导致异常。我的经验是给pop操作添加默认值'#'作为保护。

3. 最小栈（LeetCode 155）

3.1 设计要求与实现方案

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

最直接的思路是使用辅助栈同步存储最小值：

主栈正常压入元素
辅助栈压入当前最小值（新元素与辅助栈顶的较小者）

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.2 空间优化方案

辅助栈可以只存储最小值变化时的记录：

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][0]: self.min_stack.append((val, len(self.stack))) def pop(self) -> None: if self.stack: if len(self.stack) == self.min_stack[-1][1]: self.min_stack.pop() self.stack.pop()

这种方案在最小值频繁重复时能显著节省空间，但pop逻辑更复杂。实际工程中需要根据数据特点权衡选择。

4. 字符串解码（LeetCode 394）

4.1 嵌套结构的处理思路

给定一个编码字符串如 "3[a2[c]]"，返回解码后的字符串 "accaccacc"。

这类嵌套结构的问题，栈是最自然的解决方案。我们需要处理三种情况：

遇到数字：开始累积数字（注意多位数情况）
遇到字母：累积到当前字符串
遇到'['：将当前字符串和数字压栈，重置状态
遇到']'：弹出栈顶的数字和字符串，进行拼接

4.2 完整实现与调试技巧

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

调试这类问题时，建议在纸上画出栈的变化过程。常见错误包括：

数字累积时未处理多位数（如"100[abc]"）
遇到']'时拼接顺序错误（应该是前字符串+当前字符串×数字）
栈中存储的元素类型混乱（建议使用元组明确存储字符串和数字）

5. 每日温度（LeetCode 739）

5.1 单调栈的应用场景

给定每日温度列表，返回一个列表表示需要等待多少天才能遇到更暖和的温度。

这是典型的"下一个更大元素"问题，单调栈能高效解决。我们维护一个栈，存储尚未找到更高温度的日期索引。对于每一天的温度，我们检查栈顶元素对应的温度是否小于当前温度，如果是则计算天数差并弹出。

5.2 实现优化与复杂度分析

def dailyTemperatures(temperatures: List[int]) -> List[int]: stack = [] result = [0] * len(temperatures) for i, temp in enumerate(temperatures): while stack and temperatures[stack[-1]] < temp: prev_index = stack.pop() result[prev_index] = i - prev_index stack.append(i) return result

时间复杂度O(n)：每个元素最多入栈出栈各一次空间复杂度O(n)：最坏情况下栈需要存储所有元素

实际编码时容易混淆栈中存储的是温度值还是索引。存储索引更实用，因为既可以通过列表访问温度值，又可以直接计算天数差。

6. 柱状图中最大的矩形（LeetCode 84）

6.1 问题转化与单调栈变种

给定n个非负整数表示柱状图的高度，求能勾勒出的最大矩形面积。

这个问题可以转化为：对于每个柱子，找到左右两边第一个比它矮的柱子。这正好是单调栈能解决的问题，不过这次我们需要维护一个单调递增的栈。

6.2 边界处理与代码实现

def largestRectangleArea(heights: List[int]) -> int: stack = [] max_area = 0 heights = [0] + heights + [0] # 添加哨兵 for i, h in enumerate(heights): while stack and heights[stack[-1]] > h: height = heights[stack.pop()] width = i - stack[-1] - 1 max_area = max(max_area, height * width) stack.append(i) return max_area

关键技巧：