1. 栈与队列基础概念回顾在正式解题之前我们需要先明确几个核心概念。栈Stack是一种后进先出LIFO的数据结构只允许在一端称为栈顶进行插入和删除操作。想象一下餐厅里叠放的餐盘你总是取走最上面的那个新洗好的盘子也会放在最上面。队列Queue则是先进先出FIFO的结构就像排队买票的队伍先来的人先得到服务。它有两个基本操作入队enqueue在队尾添加元素出队dequeue从队首移除元素。在力扣题目中这两种数据结构经常以各种变形出现单调栈栈内元素保持单调递增或递减双端队列两端都可以进行插入和删除操作优先队列元素带有优先级出队顺序由优先级决定实际面试中面试官可能会要求你手写这些数据结构的实现。建议至少掌握数组和链表两种实现方式。2. 栈的经典题目解析2.1 有效的括号LeetCode 20这是栈结构最经典的入门题。给定一个只包含 (, ), {, }, [ 和 ] 的字符串判断字符串是否有效。解题思路初始化一个空栈遍历字符串遇到左括号就压栈遇到右括号就检查栈顶是否匹配匹配则弹出栈顶不匹配直接返回false最后检查栈是否为空def isValid(s: str) - bool: stack [] mapping {): (, }: {, ]: [} 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 stack常见错误忘记处理栈为空时pop的情况或者最后没有检查栈是否为空。2.2 每日温度LeetCode 739给定一个温度列表要求返回一个列表表示需要等待多少天才能等到更暖和的温度。这是单调栈的典型应用。解法分析维护一个单调递减栈存储的是日期索引当当前温度大于栈顶温度时计算日期差并记录结果def dailyTemperatures(T: List[int]) - List[int]: stack [] res [0] * len(T) for i in range(len(T)): while stack and T[i] T[stack[-1]]: prev stack.pop() res[prev] i - prev stack.append(i) return res时间复杂度分析虽然看起来有嵌套循环但每个元素最多入栈出栈一次所以是O(n)时间复杂度。3. 队列的经典题目解析3.1 用栈实现队列LeetCode 232这道题要求使用栈的FILO特性来实现队列的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: self._transfer() return self.out_stack.pop() def peek(self) - int: self._transfer() return self.out_stack[-1] def _transfer(self): if not self.out_stack: while self.in_stack: self.out_stack.append(self.in_stack.pop())面试陷阱面试官可能会追问各个操作的时间复杂度。最好情况O(1)最坏情况O(n)但均摊分析仍然是O(1)。3.2 滑动窗口最大值LeetCode 239这是单调队列的经典应用。给定一个数组和滑动窗口大小k找出每个窗口中的最大值。高效解法使用双端队列存储可能成为窗口最大值的元素索引队列中的元素按从大到小排列当新元素大于队尾元素时弹出队尾元素维护单调性检查队首元素是否还在窗口内def maxSlidingWindow(nums: List[int], k: int) - List[int]: from collections import deque q deque() res [] for i in range(len(nums)): while q and nums[i] nums[q[-1]]: q.pop() q.append(i) if q[0] i - k: q.popleft() if i k - 1: res.append(nums[q[0]]) return res时间复杂度每个元素最多入队出队一次O(n)时间复杂度。4. 栈与队列的混合应用4.1 用队列实现栈LeetCode 225与232题相反这次要用队列的FIFO特性实现栈的FILO特性。有两种主要实现方式方法一两个队列push时O(1)pop时O(n)入栈时直接加入非空队列出栈时将非空队列的前n-1个元素转移到另一个队列然后弹出最后一个元素方法二一个队列push时O(n)pop时O(1)入栈时先将新元素入队然后把前面的元素依次出队再入队出栈时直接出队# 方法二实现 class MyStack: def __init__(self): self.q collections.deque() def push(self, x: int) - None: self.q.append(x) for _ in range(len(self.q) - 1): self.q.append(self.q.popleft()) def pop(self) - int: return self.q.popleft()实际应用中根据使用场景选择实现方式。如果push操作频繁选择方法一如果pop操作频繁选择方法二。4.2 逆波兰表达式求值LeetCode 150这是栈在表达式求值中的典型应用。逆波兰表达式后缀表达式的特点是操作符在操作数之后。解题步骤初始化一个空栈遍历tokens遇到数字就压栈遇到操作符就弹出栈顶两个元素进行计算将结果压栈最后栈中剩下的就是结果def evalRPN(tokens: List[str]) - int: stack [] for token in tokens: if token not in -*/: stack.append(int(token)) else: b stack.pop() a stack.pop() if token : stack.append(a b) elif token -: stack.append(a - b) elif token *: stack.append(a * b) else: stack.append(int(a / b)) # 注意除法向零取整 return stack[0]特别注意Python的除法与题目要求可能不同需要使用int(a/b)而不是a//b因为//是向下取整。5. 高级应用与变形题目5.1 最小栈LeetCode 155设计一个支持push、pop、top操作并能在常数时间内检索到最小元素的栈。解法思路使用辅助栈同步记录当前最小值主栈压入元素时辅助栈压入当前最小值主栈弹出时辅助栈同步弹出class MinStack: def __init__(self): self.stack [] self.min_stack [float(inf)] def push(self, val: int) - None: self.stack.append(val) self.min_stack.append(min(val, 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]空间优化辅助栈可以不存储所有状态只在遇到更小值时入栈等于当前最小值时也入栈。5.2 接雨水LeetCode 42这道题可以用单调栈、双指针或动态规划多种方法解决。这里展示单调栈解法def trap(height: List[int]) - int: stack [] res 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] width i - left - 1 bounded_height min(height[left], height[i]) - height[bottom] res width * bounded_height stack.append(i) return res理解要点栈中存储的是递减的柱子的索引当遇到更高的柱子时计算前面能接的雨水量雨水量 宽度 × (左右边界较小值 - 底部高度)6. 面试实战技巧与常见错误6.1 面试中的高频考点根据力扣和各大公司的面试统计栈与队列相关题目常考以下类型基础实现题用栈实现队列等括号匹配类问题单调栈应用接雨水、柱状图最大矩形滑动窗口问题表达式求值6.2 常见错误与调试技巧边界条件处理不足栈/队列为空时的操作输入为空或只有一个元素的情况数值溢出特别是Python不需要考虑但其他语言要注意复杂度分析错误误认为嵌套循环就是O(n²)忽略均摊分析如用栈实现队列的操作调试建议对于复杂问题先手动模拟小例子打印栈/队列的状态变化使用assert检查不变式6.3 性能优化思路空间换时间最小栈的辅助栈预处理某些信息如单调栈问题中预先计算左右边界算法选择滑动窗口问题优先考虑单调队列最近相关性问题如括号匹配优先考虑栈语言特性利用Python中collections.deque比list更适合队列实现某些情况下可以用位运算替代栈操作如括号匹配可以用计数器我在实际面试和刷题中发现很多同学对栈和队列的理解停留在表面。建议不仅要会做题还要理解每个操作背后的计算机科学原理。比如函数调用栈、消息队列在实际系统中的应用这些深度理解会让你在面试中脱颖而出。
1. 栈与队列基础概念回顾在正式解题之前我们需要先明确几个核心概念。栈Stack是一种后进先出LIFO的数据结构只允许在一端称为栈顶进行插入和删除操作。想象一下餐厅里叠放的餐盘你总是取走最上面的那个新洗好的盘子也会放在最上面。队列Queue则是先进先出FIFO的结构就像排队买票的队伍先来的人先得到服务。它有两个基本操作入队enqueue在队尾添加元素出队dequeue从队首移除元素。在力扣题目中这两种数据结构经常以各种变形出现单调栈栈内元素保持单调递增或递减双端队列两端都可以进行插入和删除操作优先队列元素带有优先级出队顺序由优先级决定实际面试中面试官可能会要求你手写这些数据结构的实现。建议至少掌握数组和链表两种实现方式。2. 栈的经典题目解析2.1 有效的括号LeetCode 20这是栈结构最经典的入门题。给定一个只包含 (, ), {, }, [ 和 ] 的字符串判断字符串是否有效。解题思路初始化一个空栈遍历字符串遇到左括号就压栈遇到右括号就检查栈顶是否匹配匹配则弹出栈顶不匹配直接返回false最后检查栈是否为空def isValid(s: str) - bool: stack [] mapping {): (, }: {, ]: [} 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 stack常见错误忘记处理栈为空时pop的情况或者最后没有检查栈是否为空。2.2 每日温度LeetCode 739给定一个温度列表要求返回一个列表表示需要等待多少天才能等到更暖和的温度。这是单调栈的典型应用。解法分析维护一个单调递减栈存储的是日期索引当当前温度大于栈顶温度时计算日期差并记录结果def dailyTemperatures(T: List[int]) - List[int]: stack [] res [0] * len(T) for i in range(len(T)): while stack and T[i] T[stack[-1]]: prev stack.pop() res[prev] i - prev stack.append(i) return res时间复杂度分析虽然看起来有嵌套循环但每个元素最多入栈出栈一次所以是O(n)时间复杂度。3. 队列的经典题目解析3.1 用栈实现队列LeetCode 232这道题要求使用栈的FILO特性来实现队列的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: self._transfer() return self.out_stack.pop() def peek(self) - int: self._transfer() return self.out_stack[-1] def _transfer(self): if not self.out_stack: while self.in_stack: self.out_stack.append(self.in_stack.pop())面试陷阱面试官可能会追问各个操作的时间复杂度。最好情况O(1)最坏情况O(n)但均摊分析仍然是O(1)。3.2 滑动窗口最大值LeetCode 239这是单调队列的经典应用。给定一个数组和滑动窗口大小k找出每个窗口中的最大值。高效解法使用双端队列存储可能成为窗口最大值的元素索引队列中的元素按从大到小排列当新元素大于队尾元素时弹出队尾元素维护单调性检查队首元素是否还在窗口内def maxSlidingWindow(nums: List[int], k: int) - List[int]: from collections import deque q deque() res [] for i in range(len(nums)): while q and nums[i] nums[q[-1]]: q.pop() q.append(i) if q[0] i - k: q.popleft() if i k - 1: res.append(nums[q[0]]) return res时间复杂度每个元素最多入队出队一次O(n)时间复杂度。4. 栈与队列的混合应用4.1 用队列实现栈LeetCode 225与232题相反这次要用队列的FIFO特性实现栈的FILO特性。有两种主要实现方式方法一两个队列push时O(1)pop时O(n)入栈时直接加入非空队列出栈时将非空队列的前n-1个元素转移到另一个队列然后弹出最后一个元素方法二一个队列push时O(n)pop时O(1)入栈时先将新元素入队然后把前面的元素依次出队再入队出栈时直接出队# 方法二实现 class MyStack: def __init__(self): self.q collections.deque() def push(self, x: int) - None: self.q.append(x) for _ in range(len(self.q) - 1): self.q.append(self.q.popleft()) def pop(self) - int: return self.q.popleft()实际应用中根据使用场景选择实现方式。如果push操作频繁选择方法一如果pop操作频繁选择方法二。4.2 逆波兰表达式求值LeetCode 150这是栈在表达式求值中的典型应用。逆波兰表达式后缀表达式的特点是操作符在操作数之后。解题步骤初始化一个空栈遍历tokens遇到数字就压栈遇到操作符就弹出栈顶两个元素进行计算将结果压栈最后栈中剩下的就是结果def evalRPN(tokens: List[str]) - int: stack [] for token in tokens: if token not in -*/: stack.append(int(token)) else: b stack.pop() a stack.pop() if token : stack.append(a b) elif token -: stack.append(a - b) elif token *: stack.append(a * b) else: stack.append(int(a / b)) # 注意除法向零取整 return stack[0]特别注意Python的除法与题目要求可能不同需要使用int(a/b)而不是a//b因为//是向下取整。5. 高级应用与变形题目5.1 最小栈LeetCode 155设计一个支持push、pop、top操作并能在常数时间内检索到最小元素的栈。解法思路使用辅助栈同步记录当前最小值主栈压入元素时辅助栈压入当前最小值主栈弹出时辅助栈同步弹出class MinStack: def __init__(self): self.stack [] self.min_stack [float(inf)] def push(self, val: int) - None: self.stack.append(val) self.min_stack.append(min(val, 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]空间优化辅助栈可以不存储所有状态只在遇到更小值时入栈等于当前最小值时也入栈。5.2 接雨水LeetCode 42这道题可以用单调栈、双指针或动态规划多种方法解决。这里展示单调栈解法def trap(height: List[int]) - int: stack [] res 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] width i - left - 1 bounded_height min(height[left], height[i]) - height[bottom] res width * bounded_height stack.append(i) return res理解要点栈中存储的是递减的柱子的索引当遇到更高的柱子时计算前面能接的雨水量雨水量 宽度 × (左右边界较小值 - 底部高度)6. 面试实战技巧与常见错误6.1 面试中的高频考点根据力扣和各大公司的面试统计栈与队列相关题目常考以下类型基础实现题用栈实现队列等括号匹配类问题单调栈应用接雨水、柱状图最大矩形滑动窗口问题表达式求值6.2 常见错误与调试技巧边界条件处理不足栈/队列为空时的操作输入为空或只有一个元素的情况数值溢出特别是Python不需要考虑但其他语言要注意复杂度分析错误误认为嵌套循环就是O(n²)忽略均摊分析如用栈实现队列的操作调试建议对于复杂问题先手动模拟小例子打印栈/队列的状态变化使用assert检查不变式6.3 性能优化思路空间换时间最小栈的辅助栈预处理某些信息如单调栈问题中预先计算左右边界算法选择滑动窗口问题优先考虑单调队列最近相关性问题如括号匹配优先考虑栈语言特性利用Python中collections.deque比list更适合队列实现某些情况下可以用位运算替代栈操作如括号匹配可以用计数器我在实际面试和刷题中发现很多同学对栈和队列的理解停留在表面。建议不仅要会做题还要理解每个操作背后的计算机科学原理。比如函数调用栈、消息队列在实际系统中的应用这些深度理解会让你在面试中脱颖而出。
