栈与队列实战：逆波兰表达式与滑动窗口最大值

1. 栈与队列实战从逆波兰表达式到滑动窗口最大值作为一名算法工程师我经常需要处理各种数据结构相关的问题。今天想和大家分享三个经典的栈与队列应用场景逆波兰表达式求值、滑动窗口最大值和前K个高频元素。这些题目看似简单但其中蕴含着栈和队列的精妙设计思想。1.1 数据结构的选择之道在解决算法问题时选择合适的数据结构往往能事半功倍。栈和队列作为线性表的特殊形式它们最大的特点就是操作受限——栈是后进先出(LIFO)队列是先进先出(FIFO)。这种限制反而让它们在某些场景下大放异彩。提示当问题需要最近相关性时考虑栈需要先进先出时考虑队列。2. 逆波兰表达式求值2.1 理解逆波兰表示法逆波兰表达式Reverse Polish NotationRPN也叫后缀表达式是一种不需要括号就能明确运算顺序的表示方法。它的核心特点是运算符位于两个操作数之后。传统的中缀表达式(1 2) * 3对应的逆波兰表达式是1 2 3 *。这种表示法的优势在于完全消除了括号的歧义运算顺序由运算符位置唯一确定非常适合用栈结构来计算2.2 算法实现详解实现逆波兰表达式求值的关键在于利用栈的LIFO特性class Solution { public int evalRPN(String[] tokens) { DequeInteger stack new LinkedList(); for (String token : tokens) { if (isOperator(token)) { int num2 stack.pop(); int num1 stack.pop(); stack.push(calculate(num1, num2, token)); } else { stack.push(Integer.parseInt(token)); } } return stack.pop(); } private boolean isOperator(String s) { return s.equals() || s.equals(-) || s.equals(*) || s.equals(/); } private int calculate(int a, int b, String op) { switch (op) { case : return a b; case -: return a - b; case *: return a * b; case /: return a / b; // 注意整数除法向零截断 default: throw new IllegalArgumentException(); } } }2.3 关键点与边界处理操作数顺序减法和除法要注意操作数顺序先弹出的是右操作数除法处理Java中整数除法本身就是向零截断与题目要求一致异常处理实际工程中需要处理非法表达式的情况栈的大小确保每次运算时栈中至少有两个操作数注意在LeetCode环境下可以假设输入总是合法的但实际开发中必须考虑各种异常情况。3. 滑动窗口最大值3.1 问题分析与暴力解法给定一个数组和窗口大小k我们需要找出所有滑动窗口中的最大值。最直观的解法是对于每个窗口遍历其中的元素找出最大值时间复杂度为O(nk)。当n很大时比如题目中的10^4量级这种解法显然不够高效。我们需要一种能在O(1)时间内获取当前窗口最大值的方法。3.2 单调队列的妙用这里引入单调队列的概念——保持队列中的元素单调递减这样队首元素就是当前窗口的最大值。关键在于维护这个单调性class MonotonicQueue { DequeInteger deque new LinkedList(); void push(int val) { // 移除所有小于当前值的元素保持队列单调递减 while (!deque.isEmpty() val deque.getLast()) { deque.removeLast(); } deque.addLast(val); } void pop(int val) { // 只有当要移除的元素等于队首时才移除 if (!deque.isEmpty() val deque.getFirst()) { deque.removeFirst(); } } int max() { return deque.getFirst(); } } class Solution { public int[] maxSlidingWindow(int[] nums, int k) { if (nums.length 0 || k 0) return new int[0]; MonotonicQueue window new MonotonicQueue(); int[] result new int[nums.length - k 1]; // 初始化第一个窗口 for (int i 0; i k; i) { window.push(nums[i]); } result[0] window.max(); // 滑动窗口 for (int i k; i nums.length; i) { window.pop(nums[i - k]); // 移除左边界的元素 window.push(nums[i]); // 添加右边界的元素 result[i - k 1] window.max(); } return result; } }3.3 复杂度分析与优化时间复杂度每个元素最多被添加和移除一次因此均摊时间复杂度为O(n)空间复杂度O(k)最坏情况下队列中存储k个元素实际测试表明这种解法比使用优先队列堆的O(nlogk)解法快3-5倍。4. 前K个高频元素4.1 统计频率与优先队列这个问题可以分为两步统计每个元素出现的频率使用HashMap找出频率最高的k个元素使用最小堆class Solution { public int[] topKFrequent(int[] nums, int k) { // 统计频率 MapInteger, Integer frequencyMap new HashMap(); for (int num : nums) { frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) 1); } // 使用最小堆保存top k PriorityQueueMap.EntryInteger, Integer heap new PriorityQueue((a, b) - a.getValue() - b.getValue()); for (Map.EntryInteger, Integer entry : frequencyMap.entrySet()) { heap.offer(entry); if (heap.size() k) { heap.poll(); // 移除频率最小的元素 } } // 收集结果 int[] result new int[k]; for (int i k - 1; i 0; i--) { result[i] heap.poll().getKey(); } return result; } }4.2 为什么使用最小堆使用最小堆而不是最大堆的原因是我们只需要维护前k大的元素不需要维护完整的排序当堆大小超过k时可以快速移除最小的元素堆顶最终堆中剩下的就是前k大的元素4.3 复杂度分析统计频率O(n)建堆操作O(nlogk)总体复杂度O(nlogk)如果k接近n可以考虑使用快速选择算法将复杂度降低到O(n)。5. 栈与队列的通用解题思路通过这三个题目我们可以总结出栈和队列在算法问题中的常见应用模式5.1 栈的典型应用场景表达式求值如逆波兰表达式括号匹配检查括号是否有效嵌套函数调用栈模拟程序执行流程深度优先搜索回溯算法的实现基础5.2 队列的典型应用场景滑动窗口问题如求滑动窗口最大值广度优先搜索树的层序遍历图的BFS任务调度实现生产者-消费者模式缓存系统如LRU缓存淘汰算法5.3 选择数据结构的思考框架是否需要保持元素的插入顺序是考虑队列或双端队列否考虑栈或优先队列是否需要快速访问最大值/最小值是考虑单调栈/队列或堆操作是否主要在序列的两端进行是考虑双端队列是否需要后进先出的特性是使用栈6. 实际编码中的注意事项6.1 Java中的实现选择栈虽然Java有Stack类但推荐使用Deque接口的实现DequeInteger stack new ArrayDeque();队列根据需求选择QueueInteger queue new LinkedList(); // 普通队列 DequeInteger deque new ArrayDeque(); // 双端队列 PriorityQueueInteger heap new PriorityQueue(); // 优先队列6.2 边界条件处理空集合处理单个元素处理重复元素处理极端大小窗口(k1或kn)数值边界整数溢出6.3 调试技巧打印中间状态栈/队列内容使用小规模测试用例检查操作顺序是否符合预期特别注意pop/peek操作前的非空检查7. 性能优化实战经验7.1 逆波兰表达式的优化使用数组模拟栈可以减少对象创建开销提前预判运算符可以减少重复判断使用switch-case比if-else链更高效7.2 滑动窗口的优化存储数组索引而非值可以减少内存占用在队列中维护可能成为最大值的候选对于特定数据分布如已排序数组可以有更优解7.3 Top K问题的优化当k接近n时可以考虑直接排序后取前k个使用快速选择算法可以达到O(n)时间复杂度对于数据流场景可以使用计数排序的思路8. 扩展思考与练习题8.1 相关变形题目基本计算器实现带括号和优先级的表达式求值每日温度使用单调栈解决下一个更高温度问题接雨水经典的单调栈应用设计循环队列实现高效的循环队列数据流的中位数使用双堆维护动态数据的中位数8.2 系统设计中的应用浏览器历史记录使用双栈实现前进后退功能任务调度系统优先队列实现任务优先级调度消息队列实现生产者和消费者的解耦撤销操作使用栈记录操作历史8.3 推荐练习路径先掌握栈和队列的基本操作理解单调栈和单调队列的工作原理练习经典问题如本文的三个题目尝试解决变形题目和系统设计问题在实际项目中寻找应用场景通过系统地学习和练习你会发现栈和队列这两个基础数据结构能解决许多看似复杂的问题。关键在于理解它们的特性和适用场景并在实际问题中灵活运用。