栈、滑动窗口与堆：算法面试高频题解析

1. 算法训练营第十天内容概览今天的三道题目分别来自栈与队列、滑动窗口和堆的应用场景。150题逆波兰表达式考察栈的基本操作239题滑动窗口最大值需要设计特殊数据结构347题前K个高频元素则是堆的典型应用。这三道题在笔试面试中出现频率极高特别是滑动窗口问题在系统设计领域也有广泛应用。2. 逆波兰表达式求值2.1 表达式转换原理逆波兰表达式后缀表达式的计算过程完美契合栈的特性。与中缀表达式不同它不需要括号来指定运算顺序运算符总是作用于最近的两个操作数。例如中缀表达式3 4 * 2转换为后缀表达式就是3 4 2 * 。关键点遇到数字入栈遇到运算符则弹出栈顶两个元素运算后将结果入栈2.2 Python实现细节from operator import add, sub, mul def div(x, y): # 处理Python负数除法的特殊情况 return int(x/y) if x*y 0 else -(abs(x)//abs(y)) class Solution: op_map {:add, -:sub, *:mul, /:div} def evalRPN(self, tokens: List[str]) - int: stack [] for token in tokens: if token not in self.op_map: stack.append(int(token)) else: op2 stack.pop() op1 stack.pop() stack.append(self.op_map[token](op1, op2)) return stack.pop()常见错误操作数顺序错误减法除法要注意操作数顺序类型转换遗漏字符串转整数不能忘除法处理不当Python的负数除法需要特殊处理3. 滑动窗口最大值3.1 单调队列设计常规暴力解法时间复杂度O(nk)使用单调队列可优化到O(n)。核心思想是维护一个可能成为窗口最大值的候选队列。from collections import deque class MonotonicQueue: def __init__(self): self.queue deque() def push(self, val): # 维护队列单调递减 while self.queue and val self.queue[-1]: self.queue.pop() self.queue.append(val) def pop(self, val): # 只有要移除的值是当前最大值时才出队 if self.queue and val self.queue[0]: self.queue.popleft() def max(self): return self.queue[0]3.2 滑动窗口实现def maxSlidingWindow(nums: List[int], k: int) - List[int]: mq MonotonicQueue() res [] # 初始化第一个窗口 for i in range(k): mq.push(nums[i]) res.append(mq.max()) # 滑动窗口 for i in range(k, len(nums)): mq.pop(nums[i-k]) # 移除离开窗口的元素 mq.push(nums[i]) # 添加新进入窗口的元素 res.append(mq.max()) return res优化技巧队列存储索引而非值方便判断元素是否在窗口内使用双端队列比列表操作更快提前分配结果列表空间减少内存分配开销4. 前K个高频元素4.1 堆的应用原理小顶堆的堆顶总是最小元素维护一个大小为K的堆当新元素频率大于堆顶时替换最终剩下的就是前K高频元素。4.2 完整实现import heapq def topKFrequent(nums: List[int], k: int) - List[int]: freq_map {} for num in nums: freq_map[num] freq_map.get(num, 0) 1 min_heap [] for num, freq in freq_map.items(): if len(min_heap) k: heapq.heappush(min_heap, (freq, num)) else: if freq min_heap[0][0]: heapq.heappop(min_heap) heapq.heappush(min_heap, (freq, num)) return [item[1] for item in min_heap]进阶优化使用快速选择算法可以达到O(n)时间复杂度对于海量数据可以考虑分治多路归并实际工程中可以结合哈希表和堆外存储处理超大数据5. 常见问题排查5.1 逆波兰表达式问题栈空异常检查表达式合法性运算顺序错误注意减法和除法的操作数顺序除法舍入Python的//运算符与题目要求可能不同5.2 滑动窗口问题窗口大小变化处理k0或kn的情况队列维护错误确保单调性不被破坏边界条件处理前k个元素时的初始化5.3 堆应用问题频次统计错误负数或零需要特殊处理吗堆大小控制k值大于元素种类数时的处理输出顺序题目是否要求按频率排序输出6. 工程实践建议逆波兰表达式计算器可以扩展支持更多运算符滑动窗口算法在实时流处理系统中很常见前K高频元素算法可用于热点数据统计三种算法组合可以解决更复杂的系统设计问题在实际编码时建议先写出暴力解法再逐步优化。理解每个数据结构的适用场景比死记硬背更重要。我在面试候选人时最看重的就是能否清晰解释算法选择的原因。