刷算法题的人应该都有这种体会有些题第一次看答案觉得“也不难嘛”真让自己写却总是卡在某个边界条件上。力扣239滑动窗口最大值就是典型它考的不只是“会遍历数组”还考察你能否在窗口滑动的动态过程中用一个合适的数据结构持续拿到最大值。Java解法里最经典也最常用的是双端队列维护一条“单调队列”把时间复杂度压到O(n)。这篇文章写给正在刷题、准备面试的同学也写给想把双端队列用法彻底吃透的人我会从暴力解法为什么超时讲起一直讲到可运行的Java代码、边界测试和面试追问中间的坑保证你看完能直接照着写。1. 先看题面为什么暴力解会被判超时1.1 题面到底在问什么题目给定一个整数数组nums和一个窗口大小k窗口从数组最左侧开始每次向右滑动一个位置最终要返回一个数组里面是每个窗口内k个元素的最大值。举个例子nums [1,3,-1,-3,5,3,6,7]k 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]。这里有一点非常容易被忽略窗口是“先进先出”的结构每次都从右边进一个新元素从左边走一个旧元素。但最大值本身不像队列头那样固定它可能在新元素进来时被替换也可能在旧元素被移走时跟着消失。正因为“最大值的生命周期”和“窗口的滑动节奏”不是一一对应的这题才需要专门设计算法。1.2 暴力解法的时间账最直观的想法是每次窗口滑动直接遍历窗口里的k个元素找出最大值。public int[] maxSlidingWindowViolent(int[] nums, int k) { int n nums.length; int[] res new int[n - k 1]; for (int i 0; i n - k; i) { int max nums[i]; for (int j i; j i k; j) { max Math.max(max, nums[j]); } res[i] max; } return res; }逻辑没错但复杂度是O(n*k)。假设n 10^5k 5 * 10^4那约等于5 * 10^9次比较Java 跑起来基本直接超时。更麻烦的是即便k比较小比如k 10、n 10^6那也是10^7级别勉强能跑可一旦数据量上涨就兜不住。力扣给这道题的定位就是要求在线性时间内解决问题暴力思路只能用来验证小数据样本不能作为最终提交方案。1.3 为什么“记住当前最大值”也不行有人会想那我维护一个max变量每次滑动只比较新进来的数和当前max不就行了吗这里有个反例窗口[3,1,2]当前最大值是3窗口右移变成[1,2,4]移走的是最大值3。如果你只记录max 3新元素4比它大还能更新成4但如果是窗口[3,1,2]右移成[1,2,0]移走3之后新的最大值实际上应该是2可你的max仍然是3这就是错的。所以问题的本质在于当最大值离开窗口后你需要立刻知道剩下的元素里“第二名”是谁。普通变量没法保存这种候选顺序你得用一个有顺序、能两头操作的数据结构来维护候选项。双端队列就是为这个需求量身定做的。2. 双端队列的解体思路让候选最大值排队2.1 为什么是Deque而不是PriorityQueue很多刷题者第一反应是用大顶堆每次新元素入堆堆顶就是最大值堆顶如果已经滑出窗口就删除。这个思路很简单但并不是最优解。用堆维护的最大问题是“懒删除”会留下过期元素。每次取堆顶时你要先判断它的下标是否还在窗口内不在就弹出但这些过期元素可能很长一段时间都堆在堆里占据堆顶位置后反复被弹出内耗很大。堆的每次插入和删除都是O(log k)总复杂度O(n log k)。双端队列则完全不同。它可以在队首弹出过期元素在队尾插入新元素并且通过单调性保证队首随时就是当前窗口最大值。因为每个元素最多入队一次、出队一次整体均摊O(1)总复杂度O(n)。我把两种方案的区别整理成一张表面试时可以直接拿来解释方案数据结构复杂度过期元素处理面试评价大顶堆PriorityQueueO(n log k)延迟删除堆中可能堆积思路容易但不够“漂亮”单调队列双端队列O(n)队首立刻弹出无堆积最优解之一面试加分2.2 单调队列维护的两个核心规则所谓单调队列这里特指“从队首到队尾下标逐渐增大元素值逐渐减小”的队列。它维护的不是窗口里的全部元素而是“有可能成为后续窗口最大值”的候选者。维护规则只有两条新元素入队时从队尾开始把所有小于等于新元素的值全部弹出。因为这些值既没有新元素大又比新元素更早过期留着永远不会被选中。窗口滑动导致队首元素的下标超出窗口范围时把队首弹出。因为窗口已经把它“送走”了它再也没有资格参与最大值评选。这两条规则一个负责“过期清理”一个负责“能力淘汰”配合起来就能让队列始终保持从大到小的递减状态。这里特别说一下等号的处理。规则一用的是“小于等于”也就是nums[deque.peekLast()] nums[i]时弹队尾。当两个元素值相等时右边的元素下标更大意味着它在窗口里存活时间更长所以应该保留右边的。比如窗口里同时有下标2的值5和下标5的值5后者更晚过期自然更有资格替代前者。2.3 队列里存下标而不是存值这是好多新手写这道题时最容易犯迷糊的地方为什么队列里不直接存int值而非要存下标原因有两点判断过期需要下标。队首是否还在当前窗口内需要拿它的下标和i - k比较如果只存值根本没法判断。比较大小也需要通过下标取原数组的值。队列里存的是下标比较时写成nums[deque.peekLast()] nums[i]取值时写成nums[deque.peekFirst()]。其实存值也不是完全不行但那样还必须额外存一个下标结构两个人同时维护操作起来更复杂。存下标其实是把“值和位置”这两个信息合二为一了因为通过下标一定能取到值。3. Java实现与代码逐段拆解3.1 完整可运行的代码先贴上完整代码后面再逐段拆import java.util.ArrayDeque; import java.util.Deque; class Solution { public int[] maxSlidingWindow(int[] nums, int k) { if (nums null || nums.length 0) { return new int[0]; } int n nums.length; int[] res new int[n - k 1]; DequeInteger deque new ArrayDeque(); for (int i 0; i n; i) { // 1. 清理窗口外过期的队首 while (!deque.isEmpty() deque.peekFirst() i - k) { deque.pollFirst(); } // 2. 清理队尾所有“打不过新元素”的候选 while (!deque.isEmpty() nums[deque.peekLast()] nums[i]) { deque.pollLast(); } // 3. 新元素下标入队 deque.offerLast(i); // 4. 窗口形成之后队首就是当前窗口最大值 if (i k - 1) { res[i - k 1] nums[deque.peekFirst()]; } } return res; } }这段代码里有一处需要特别说明为什么用ArrayDeque而不是LinkedList。ArrayDeque底层是循环数组对 CPU 缓存更友好实测表现通常比链表实现的LinkedList稳定而且它不允许null元素而我们队列里存的是下标永远不会是null所以没有副作用。JDK 的Deque接口提供了peekFirst、pollFirst、peekLast、pollLast、offerLast这些方法正好覆盖这道题所需的所有操作。3.2 四个关键步骤的顺序为什么不能乱第一步“清理过期队首”放在最前面是为了让后面对队尾的每一项操作都建立在“队列里的下标都属于当前窗口”这个前提下。如果不先清理队首可能还残留一个已经滑出窗口的老下标虽然它一般不影响队尾的淘汰判断但到了读取结果的那一步就会出错。第二步“队尾淘汰”是单调队列的灵魂。每次新来一个元素nums[i]把队尾所有小于等于它的下标弹出。这步做掉之后队列里的元素值从头到尾严格递减。第三步把新下标放进队尾。由于前两步保证它一定能作为“现有最大值的候选者”合理入队。第四步只在窗口完整时读队首。窗口从i 0开始滑到i k - 1时第一个完整窗口才形成所以条件是i k - 1结果存到res[i - k 1]。这四个步骤的顺序我建议新手不要乱调。先清过期、再比大小、然后插入、最后读值是一个固定模板。每一步之后队列的状态都清晰可解释出了问题也容易定位。不是所有写法都必须这样但这是最不容易写错的一种。3.3 核心操作的时空复杂度推导每个元素最多入队一次、出队一次。虽然第二步的while循环里可能连续弹出多个队尾元素但每个元素被弹出一次也是这一次消耗了它的“出队机会”。总共入队n次出队最多n次所有操作加起来是O(n)均摊到每一轮循环就是常数级别。空间方面队列里最多同时存在k 1个元素吗其实不会超过k个因为队列里的下标都属于当前窗口且下标严格递增。结果数组res不算额外辅助空间所以空间复杂度是O(k)。4. 测试与边界情况只通过示例不够4.1 准备一组能覆盖细节的测试用例写算法题最忌讳“示例过了就当过了”而是要主动构造边界用例。我把自己刷这题时用来验证的用例整理如下输入numsk期望输出测试意图[1,3,-1,-3,5,3,6,7]3[3,3,5,5,6,7]题目标准示例[1]1[1]单元素数组[1,-1]1[1,-1]窗口大小为1时输出原数组[1,2,3,4,5]3[3,4,5]严格递增数组[5,4,3,2,1]3[5,4,3]严格递减数组[7,7,7,7]2[7,7,7]全部相同的数组[]或null任意[]空数组防御严格递增时每个新元素都比队尾所有元素大第二步的while会连续弹空整个队列所以队列里通常只剩一个新下标。严格递减时新元素永远“打不过”队尾第二步完全不会触发队列会一直变长等到队首元素过期时再由第一步把它弹出去。两种情况正好覆盖了单调队列两端的核心操作。4.2 易被忽略的边界条件第一数组为空或为null。代码开头直接判断nums.length 0返回空数组这是防御性编程的基本功。第二k 1。此时每个窗口只有一个元素最大值就是它本身。按代码逻辑走完全没问题但你可以观察到因为窗口长度为1队尾淘汰会把小于等于新元素的老元素弹掉队首又因为过期判断每轮都会被清空队列里始终只有当前元素结果自然等同于原数组。第三k n。整个数组只有一个窗口返回数组长度为1。代码里res长度为n - k 1 1循环结束后只会写入一次结果。第四nums为null时如果直接取nums.length会抛空指针。不过力扣的测试数据通常不会给null但养成防御习惯不是坏事。4.3 手动画一遍队列变化比背答案管用我建议刷这道题时拿[1,3,-1,-3,5,3,6,7]k3亲手画一遍单调队列的变化过程。i0队列空1入队队列[0]此时i 2不写结果。i1队首0未过期队尾比较1 3弹出下标01入队队列[1]。i2队首未过期队尾比较3 -1不成立2入队队列[1,2]窗口完整队首1对应值3写入res[0]3。i3队首1刚好等于i-k0不对i-k0队首是1没过期队尾比较-1 -3不成立3入队队列[1,2,3]取队首3写入res[1]3。走到i4队首1的下标等于1当前窗口左边界是i-k12说明下标1已经滑出窗口第一步弹掉第二步比较-3 5、-1 5、3 5一口气弹出3、2、1然后4入队写入res[2]5。你会发现每一步都符合“队首即最大”的预期。只要把这个过程在纸上演练一遍代码里四个步骤的顺序和目的就全都通了。5. 面试追问与常见错误能答透才说明真会5.1 追问一为什么时间复杂度是O(n)而不是O(n*k)这是面试官最常追问的点其实答案就一句话每个元素入队一次、出队一次所有操作次数之和不超过2n。很多人误以为第二步的while循环可能在每一轮都弹出多个元素所以不是线性的。但一个元素一旦被弹出后面就不会再进队了它能被弹的次数就是它自己的那一次“出队”。把视角从“每轮循环做了什么”切换到“每个元素被操作了几次”就明白均摊复杂度是线性的。5.2 追问二能不能用堆做两个方案怎么选堆方案适合面试时先说思路因为它直观维护一个大顶堆堆里存(值, 下标)每次新元素入堆弹出堆顶直到堆顶下标还在窗口内。代码写起来也短但复杂度是O(n log k)而且堆里的过期元素偶尔会堆积到接近n个空间表现差。如果面试官追问“能不能优化”就应该给出双端队列单调队列方案。如果笔试环境时间紧张先用堆快速拿到通过也不是不行但面试手撕代码时我推荐直接上单调队列因为面试官对这道题的期待就是看到你能写出线性方案。5.3 追问三如果数据是流式的k很大怎么办双端队列解法天然支持流式场景因为每个元素只在它到达时处理一次而且队列长度最多是k。即使k很大只要内存能放下k个下标就没问题。如果k大到连队列都放不下那就得换思路了。比如分块预计算、稀疏表之类的方案但那些往往要求数据可以离线处理不适合流式场景。面试中把这句话讲清楚基本就能体现你对这个问题的理解深度。5.4 我踩过的坑和教训第一坑过期判断的边界。窗口左边界是i - k 1所以队首下标 i - k时必须删除。我曾经写过deque.peekFirst() i - k结果最大值晚了一格才被移出返回结果里出现了已经不属于窗口的旧最大值。这个问题很隐蔽小数组测不出来一旦出现连续多个小元素夹着旧最大值的情况就会暴露。第二坑写结果之前忘记判断窗口是否完整。如果不加i k - 1就直接取队首前面k-1个不完整窗口也会被当成结果写进数组导致结果长度错乱。第三坑队尾淘汰时用了而不是。结果可能依然全对但如果面试官追问“相等的值你保留哪个、为什么”答不上来就很尴尬。养成写的习惯遇到重复值保留更靠右的元素逻辑更稳。第四坑用LinkedList或ArrayDeque时调用getFirst()、getLast()前不判空。空队列调用会抛NoSuchElementException用peekFirst()和peekLast()配合isEmpty()更安全。最后分享一个我自己的做题习惯。拿到滑动窗口相关题目先把窗口左边界公式i - k 1写在注释里再写四步循环骨架。写完之后至少跑四组用例k1、kn、全相同、完全逆序基本能覆盖所有隐藏边界。这道题的精髓不是背代码而是理解“能力淘汰”和“过期清理”这两个动作在窗口滑动的每一轮里双向维护队列。只要把队列变化过程画明白面试现场哪怕一时卡壳也能顺着队首、队尾的进出逻辑把代码推导出来。