1. 理解Hot100与栈的关系
Hot100通常指的是LeetCode平台上最热门的100道算法题集合,这些题目被高频出现在各大科技公司的面试中。而栈(Stack)作为计算机科学中最基础的数据结构之一,在Hot100题目中占据了重要地位。
栈是一种遵循LIFO(后进先出)原则的线性数据结构,就像我们日常生活中叠放的盘子,最后放上去的盘子总是最先被取走。这种特性使得栈在解决某些特定类型的问题时具有天然优势。
提示:在算法面试中,约15-20%的Hot100题目会直接或间接用到栈结构。掌握栈的应用场景可以显著提高解题效率。
2. 栈的核心特性与基本操作
2.1 栈的ADT(抽象数据类型)
栈主要支持以下基本操作:
- push:将元素压入栈顶
- pop:移除并返回栈顶元素
- peek/top:查看栈顶元素但不移除
- isEmpty:判断栈是否为空
- size:获取栈中元素数量
# Python中使用列表实现栈的基本操作 stack = [] stack.append(1) # push操作 top = stack[-1] # peek操作 item = stack.pop() # pop操作 is_empty = len(stack) == 02.2 栈的时间复杂度分析
理解栈操作的时间复杂度对算法优化至关重要:
- 所有基本操作(push/pop/peek)的时间复杂度都是O(1)
- 空间复杂度取决于存储的元素数量,通常为O(n)
- 某些语言中(如Python)使用动态数组实现的栈,在扩容时会有摊销时间复杂度
3. Hot100中栈的典型应用场景
3.1 括号匹配问题
这是栈最经典的面试题之一,例如LeetCode第20题"有效的括号"。解题思路是:
- 遇到左括号就压栈
- 遇到右括号就弹出栈顶元素并检查是否匹配
- 最后检查栈是否为空
def isValid(s: str) -> bool: mapping = {')':'(', '}':'{', ']':'['} stack = [] for char in s: if char in mapping: top = stack.pop() if stack else '#' if mapping[char] != top: return False else: stack.append(char) return not stack3.2 单调栈的应用
单调栈是栈的一种特殊用法,用于解决"下一个更大元素"这类问题。例如LeetCode第739题"每日温度":
def dailyTemperatures(T: List[int]) -> List[int]: stack = [] result = [0] * len(T) for i, temp in enumerate(T): while stack and T[stack[-1]] < temp: prev = stack.pop() result[prev] = i - prev stack.append(i) return result这种解法的时间复杂度是O(n),比暴力解法O(n²)高效得多。
3.3 表达式求值
栈在处理表达式求值(如LeetCode第224题"基本计算器")时也非常有用。通常需要两个栈:
- 操作数栈:存储数字
- 运算符栈:存储运算符和括号
注意:处理运算符优先级时,需要比较栈顶运算符和当前运算符的优先级,决定是否立即计算。
4. 栈与其他数据结构的组合应用
4.1 双栈实现队列
LeetCode第232题"用栈实现队列"展示了如何用两个栈模拟队列的FIFO特性:
class MyQueue: def __init__(self): self.in_stack = [] self.out_stack = [] def push(self, x: int) -> None: self.in_stack.append(x) def pop(self) -> int: if not self.out_stack: while self.in_stack: self.out_stack.append(self.in_stack.pop()) return self.out_stack.pop()4.2 栈与哈希表的结合
在某些问题中,如LeetCode第496题"下一个更大元素I",需要结合哈希表来优化查找:
def nextGreaterElement(nums1: List[int], nums2: List[int]) -> List[int]: stack = [] mapping = {} for num in nums2: while stack and num > stack[-1]: mapping[stack.pop()] = num stack.append(num) return [mapping.get(num, -1) for num in nums1]5. 栈在递归问题中的应用
5.1 用栈模拟递归
许多递归算法可以显式地用栈来实现,避免递归带来的栈溢出风险。例如二叉树的中序遍历:
def inorderTraversal(root: TreeNode) -> List[int]: stack, result = [], [] curr = root while curr or stack: while curr: stack.append(curr) curr = curr.left curr = stack.pop() result.append(curr.val) curr = curr.right return result5.2 递归问题的迭代解法
LeetCode第394题"字符串解码"展示了如何用栈处理嵌套结构:
def decodeString(s: str) -> str: stack = [] curr_str = "" curr_num = 0 for char in s: if char == '[': stack.append((curr_str, curr_num)) curr_str = "" curr_num = 0 elif char == ']': prev_str, num = stack.pop() curr_str = prev_str + num * curr_str elif char.isdigit(): curr_num = curr_num * 10 + int(char) else: curr_str += char return curr_str6. 栈在Hot100中的高级应用
6.1 最大矩形问题
LeetCode第84题"柱状图中最大的矩形"展示了栈在解决几何问题中的威力:
def largestRectangleArea(heights: List[int]) -> int: stack = [-1] max_area = 0 heights.append(0) for i in range(len(heights)): while stack[-1] != -1 and heights[stack[-1]] > heights[i]: h = heights[stack.pop()] w = i - stack[-1] - 1 max_area = max(max_area, h * w) stack.append(i) return max_area6.2 雨水收集问题
LeetCode第42题"接雨水"展示了如何用栈计算积水面积:
def trap(height: List[int]) -> int: stack = [] water = 0 for i in range(len(height)): while stack and height[i] > height[stack[-1]]: bottom = stack.pop() if not stack: break left = stack[-1] water_height = min(height[left], height[i]) - height[bottom] water += water_height * (i - left - 1) stack.append(i) return water7. 栈问题的解题技巧与常见错误
7.1 栈问题的识别特征
当遇到以下特征时,考虑使用栈:
- 需要处理嵌套结构(括号、HTML标签等)
- 需要记录历史信息以便回溯
- 问题涉及最近相关性(如最近的更大/更小元素)
- 需要反转元素的处理顺序
7.2 常见错误与调试技巧
- 边界条件处理不足:空栈时执行pop操作
- 运算符优先级处理错误:在表达式求值中常见
- 空间复杂度估算不足:大规模数据时栈可能溢出
- 单调栈维护不当:未能正确保持单调性
调试技巧:在纸上手动模拟栈操作,特别是在处理复杂逻辑时,逐步跟踪栈的状态变化。
8. 栈的变种与扩展应用
8.1 最小栈设计
LeetCode第155题"最小栈"要求设计一个能在O(1)时间内获取最小值的栈:
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) def pop(self) -> None: if self.stack.pop() == self.min_stack[-1]: self.min_stack.pop() def top(self) -> int: return self.stack[-1] def getMin(self) -> int: return self.min_stack[-1]8.2 浏览器的前进后退功能
栈可以完美模拟浏览器的历史记录功能:
- 一个栈处理后退
- 另一个栈处理前进
- 访问新页面时清空前进栈
class BrowserHistory: def __init__(self, homepage: str): self.back_stack = [homepage] self.forward_stack = [] def visit(self, url: str) -> None: self.back_stack.append(url) self.forward_stack = [] def back(self, steps: int) -> str: while steps > 0 and len(self.back_stack) > 1: self.forward_stack.append(self.back_stack.pop()) steps -= 1 return self.back_stack[-1] def forward(self, steps: int) -> str: while steps > 0 and self.forward_stack: self.back_stack.append(self.forward_stack.pop()) steps -= 1 return self.back_stack[-1]9. 栈在系统设计中的应用
9.1 函数调用栈
理解程序执行时的调用栈对调试递归和异常非常重要:
- 每次函数调用都会在栈中创建一个栈帧
- 栈帧包含局部变量、参数和返回地址
- 栈溢出通常发生在递归深度过大时
9.2 撤销操作实现
大多数编辑器的撤销功能使用双栈实现:
- 操作栈:记录所有执行的操作
- 撤销栈:记录被撤销的操作
- 重做时从撤销栈弹出并压入操作栈
10. 栈的优化技巧与高级话题
10.1 空间优化技巧
在某些问题中,可以优化栈的空间使用:
- 使用变量替代栈(如只需知道栈顶元素时)
- 复用输入数组作为栈(当允许修改输入时)
- 延迟计算(只在必要时处理栈中元素)
10.2 并行计算中的栈
在多线程环境中使用栈需要特别注意:
- 标准栈实现不是线程安全的
- 需要同步机制(如锁)保护共享栈
- 考虑使用无锁数据结构或线程本地栈
在实际面试中遇到栈相关问题时,建议先明确问题的核心需求,判断是否适合使用栈结构,然后考虑是否需要单调栈等特殊用法。多练习Hot100中的栈相关问题,可以显著提高解题速度和代码质量。