概述为什么学完栈之后要学队列上一篇我们讲了栈。栈的特点是后进先出也就是最后放进去的元素最先被取出来。而这一篇要讲的队列正好是另一种非常基础的数据结构先进先出也就是先放进去的元素先被取出来。队列在算法题里经常出现在下面这些场景按顺序处理任务模拟排队过程BFS 广度优先搜索层序遍历二叉树滑动窗口中的元素维护单调队列解决窗口最大值、最小值问题如果说栈适合处理“最近的未处理元素”那么队列更适合处理最早进入、最早应该被处理的元素。这篇文章会从普通队列讲起再过渡到双端队列最后重点讲单调队列。你需要掌握下面几件事队列的基本概念和 Java 写法队列适合解决什么问题双端队列Deque为什么重要单调队列的核心思想如何用单调队列解决滑动窗口最大值学完这篇你应该能理解队列的先进先出思想并掌握用单调队列在O(n)时间内解决窗口最值问题。核心概念队列到底是什么队列是一种遵循先进先出规则的数据结构。First In First Out可以把它想象成排队买票队头 队尾 [1] - [2] - [3] - [4] - [5] 先来的人先被服务 后来的人排在后面常见操作如下操作含义时间复杂度offer元素进入队尾O(1)poll队头元素出队O(1)peek查看队头元素O(1)isEmpty判断队列是否为空O(1)在 Java 中算法题里常用Queue或Deque来表示队列。普通队列写法importjava.util.ArrayDeque;importjava.util.Queue;QueueIntegerqueuenewArrayDeque();queue.offer(1);queue.offer(2);queue.offer(3);intfirstqueue.peek();// 1intxqueue.poll();// 1如果需要同时操作队头和队尾就使用Deque。importjava.util.ArrayDeque;importjava.util.Deque;DequeIntegerdequenewArrayDeque();deque.offerLast(1);// 队尾加入deque.offerLast(2);deque.pollFirst();// 队头弹出队列强调处理顺序谁先进入谁就先被处理。队列与栈的区别栈和队列都可以存放一组元素但它们的取出顺序完全不同。数据结构规则常见场景栈后进先出括号匹配、表达式、递归、单调栈队列先进先出BFS、层序遍历、任务调度、单调队列看一个简单例子。如果依次放入1, 2, 3栈的取出顺序是3, 2, 1队列的取出顺序是1, 2, 3所以选择栈还是队列关键要看题目需要的处理顺序如果要处理最近加入的元素优先想栈如果要处理最早加入的元素优先想队列普通队列的典型应用BFS队列最典型的应用是 BFS也就是广度优先搜索。BFS 的特点是先访问距离近的节点再访问距离远的节点。这种“按层扩展”的过程天然适合用队列。比如从节点A出发A / | \ B C D / | E FBFS 的访问顺序通常是A - B - C - D - E - F过程可以理解为先把起点A入队取出队头A把A的邻居B、C、D入队继续取出队头B再把B的邻居入队不断重复直到队列为空BFS 通用模板importjava.util.ArrayDeque;importjava.util.Queue;QueueIntegerqueuenewArrayDeque();boolean[]visitednewboolean[n];queue.offer(start);visited[start]true;while(!queue.isEmpty()){intcurqueue.poll();for(intnext:graph[cur]){if(!visited[next]){visited[next]true;queue.offer(next);}}}为什么 BFS 要用队列队列能保证先进入队列的节点先被处理。在 BFS 中先进入队列的节点通常距离起点更近。所以队列可以自然维持“按层扩展”的顺序。这也是 BFS 能解决最短步数问题的基础。后面的 BFS 专题会展开讲这里先记住队列和 BFS 的关系即可。双端队列Deque 为什么重要普通队列只能从队尾加入、从队头删除。但有些题目中我们既需要操作队头也需要操作队尾。这时就需要双端队列。Deque的全称是Double Ended Queue也就是两端都能操作的队列。常用方法如下方法含义offerFirst从队头加入offerLast从队尾加入pollFirst从队头删除pollLast从队尾删除peekFirst查看队头peekLast查看队尾示例代码DequeIntegerdequenewArrayDeque();deque.offerLast(1);// [1]deque.offerLast(2);// [1, 2]deque.offerFirst(0);// [0, 1, 2]intadeque.peekFirst();// 0intbdeque.peekLast();// 2deque.pollFirst();// [1, 2]deque.pollLast();// [1]双端队列是单调队列的基础。因为单调队列既要从队尾删除不合格元素也要从队头删除过期元素。当题目需要同时维护队头和队尾时优先考虑双端队列。进阶概念什么是单调队列单调队列是在普通队列基础上增加了一个要求队列中的元素保持单调递增或单调递减。常见有两类单调递减队列队头到队尾的值越来越小单调递增队列队头到队尾的值越来越大单调队列最经典的用途是在滑动窗口中快速得到最大值或最小值。比如数组nums [1, 3, -1, -3, 5, 3, 6, 7] k 3窗口长度为3每次向右滑动一格[1, 3, -1] 最大值 3 [3, -1, -3] 最大值 3 [-1, -3, 5] 最大值 5 [-3, 5, 3] 最大值 5 [5, 3, 6] 最大值 6 [3, 6, 7] 最大值 7输出[3, 3, 5, 5, 6, 7]如果每个窗口都暴力扫描一次时间复杂度是O(n * k)而单调队列可以把它优化到O(n)单调队列的核心思想以滑动窗口最大值为例我们要维护一个单调递减队列。队头永远保存当前窗口中的最大值下标。为什么可以做到当新元素nums[i]进入窗口时如果队尾元素比nums[i]小那么队尾元素就没用了因为nums[i]更大而且位置更靠右在之后的窗口中队尾元素不可能再成为最大值所以可以直接从队尾删除这个过程会一直重复直到队尾元素大于等于当前元素。然后把当前下标加入队尾。同时由于窗口在向右移动还要检查队头是否过期如果队头下标 i - k 说明它已经不在当前窗口内 需要从队头删除所以单调队列每轮主要做两件事1. 从队尾删除不可能成为答案的元素 2. 从队头删除已经离开窗口的元素为什么队列里通常存下标单调队列里一般不直接存值而是存数组下标。原因有两个可以通过下标判断元素是否过期可以通过nums[index]拿到元素值进行比较例如deque.peekFirst()i-k这句判断的就是队头元素是否已经离开窗口。单调队列保存的是当前窗口里仍然可能成为最大值或最小值的候选元素。经典题型滑动窗口最大值题目给定整数数组nums和窗口大小k窗口每次向右移动一位返回每个窗口中的最大值。示例输入nums [1, 3, -1, -3, 5, 3, 6, 7], k 3 输出[3, 3, 5, 5, 6, 7]暴力解法最直接的做法是枚举每个窗口然后在窗口内部找最大值。classSolution{publicint[]maxSlidingWindow(int[]nums,intk){intnnums.length;int[]ansnewint[n-k1];for(inti0;in-k;i){intmaxnums[i];for(intji;jik;j){maxMath.max(max,nums[j]);}ans[i]max;}returnans;}}复杂度时间复杂度O(n * k)空间复杂度O(1)不计输出数组如果n和k都很大这个解法很容易超时。单调队列解法我们维护一个单调递减队列。队列里存的是数组下标并且下标对应的值从队头到队尾递减。每遍历到一个位置i删除队头中过期的下标删除队尾中所有小于当前值的下标把当前下标加入队尾如果窗口已经形成就把队头对应的值加入答案Java 代码实现importjava.util.ArrayDeque;importjava.util.Deque;classSolution{publicint[]maxSlidingWindow(int[]nums,intk){intnnums.length;int[]ansnewint[n-k1];DequeIntegerdequenewArrayDeque();for(inti0;in;i){while(!deque.isEmpty()deque.peekFirst()i-k){deque.pollFirst();}while(!deque.isEmpty()nums[deque.peekLast()]nums[i]){deque.pollLast();}deque.offerLast(i);if(ik-1){ans[i-k1]nums[deque.peekFirst()];}}returnans;}}代码逐行拆解先看删除过期元素while(!deque.isEmpty()deque.peekFirst()i-k){deque.pollFirst();}当前窗口的范围是[i - k 1, i]如果队头下标小于等于i - k说明它已经不在窗口内了需要删除。再看维护单调性while(!deque.isEmpty()nums[deque.peekLast()]nums[i]){deque.pollLast();}如果队尾元素比当前元素小那么它以后不可能成为最大值。因为当前元素更大而且位置更靠右会比它在窗口里存在得更久。最后加入当前下标deque.offerLast(i);当窗口长度达到k之后队头就是当前窗口最大值if(ik-1){ans[i-k1]nums[deque.peekFirst()];}复杂度分析时间复杂度O(n)空间复杂度O(k)虽然代码里有两个while但每个下标最多入队一次、出队一次。所以整体时间复杂度是线性的。单调队列如何解决窗口最小值如果题目要求的是滑动窗口最小值只需要把单调递减队列改成单调递增队列。也就是把维护单调性的比较条件从nums[deque.peekLast()]nums[i]改成nums[deque.peekLast()]nums[i]完整代码如下importjava.util.ArrayDeque;importjava.util.Deque;classSolution{publicint[]minSlidingWindow(int[]nums,intk){intnnums.length;int[]ansnewint[n-k1];DequeIntegerdequenewArrayDeque();for(inti0;in;i){while(!deque.isEmpty()deque.peekFirst()i-k){deque.pollFirst();}while(!deque.isEmpty()nums[deque.peekLast()]nums[i]){deque.pollLast();}deque.offerLast(i);if(ik-1){ans[i-k1]nums[deque.peekFirst()];}}returnans;}}最大值和最小值的区别只有一处目标队列单调性队尾删除条件窗口最大值单调递减队尾值当前值窗口最小值单调递增队尾值当前值单调队列和单调栈的区别上一篇讲了单调栈这一篇讲单调队列。它们名字很像也确实有相似之处。共同点都维护单调性都会删除不可能成为答案的元素都能把一些暴力查找优化到O(n)不同点对比项单调栈单调队列常见问题下一个更大或更小元素滑动窗口最大值或最小值是否有窗口范围通常没有固定窗口通常有固定窗口删除位置主要从栈顶删除队头删过期队尾删劣质候选保存元素未找到答案的元素窗口内可能成为最值的候选元素可以这样理解单调栈更关注“谁能解决谁”单调队列更关注“当前窗口里谁最有资格当答案”。高频变形带限制的最短子数组单调队列除了滑动窗口最大值也常用于一些前缀和问题。例如有一类题给定数组和目标值求和至少为K的最短连续子数组长度。这类题会把原数组转成前缀和然后在前缀和数组上维护一个单调队列。核心思想仍然是队头用于尝试更新答案队尾用于删除不可能更优的候选前缀和这类题比滑动窗口最大值更难后面讲前缀和进阶或动态规划优化时可以再单独展开。初学阶段先把滑动窗口最大值吃透即可。常见坑点写单调队列最容易错在哪里1. 队列里存了值导致无法判断过期错误思路DequeIntegerdequenewArrayDeque();deque.offerLast(nums[i]);这样虽然能比较大小但无法知道这个值属于哪个下标也就无法判断它是否离开窗口。推荐写法DequeIntegerdequenewArrayDeque();deque.offerLast(i);通过下标既能取值nums[deque.peekFirst()]也能判断过期deque.peekFirst()i-k2. 先后顺序写错一般推荐顺序是删除过期元素删除队尾中不可能成为答案的元素当前下标入队窗口形成后记录答案这个顺序清晰且不容易出错。3. 把窗口边界写错当前遍历到下标i窗口大小为k当前窗口左边界是i - k 1所以过期条件是deque.peekFirst()i-k1等价写法是deque.peekFirst()i-k不要写成deque.peekFirst()i-k这会导致过期元素晚删一步。模板总结滑动窗口最大值下面是最常用的单调队列模板。int[]maxSlidingWindow(int[]nums,intk){intnnums.length;int[]ansnewint[n-k1];DequeIntegerdequenewArrayDeque();for(inti0;in;i){while(!deque.isEmpty()deque.peekFirst()i-k){deque.pollFirst();}while(!deque.isEmpty()nums[deque.peekLast()]nums[i]){deque.pollLast();}deque.offerLast(i);if(ik-1){ans[i-k1]nums[deque.peekFirst()];}}returnans;}记模板时不要只背代码可以记住它背后的四句话队头过期就删除 队尾比当前弱就删除 当前下标进入队尾 窗口形成后队头就是答案总结队列的核心特征是先进先出它适合处理按顺序推进的问题例如 BFS、层序遍历和任务调度。双端队列Deque可以同时操作队头和队尾是单调队列的基础。单调队列的核心作用是在滑动窗口中快速维护最大值或最小值。你需要重点记住普通队列用于按顺序处理元素Deque支持队头和队尾两端操作单调队列通常存下标而不是直接存值求窗口最大值时维护单调递减队列求窗口最小值时维护单调递增队列队头负责给答案队尾负责淘汰不可能成为答案的元素每个元素最多入队一次、出队一次所以整体是O(n)