剑指offer-64这道题在我刷了三遍之后终于敢说彻底吃透了。滑动窗口最大值说白了就是给你一个数组和一个固定长度的窗口窗口从左往右滑每滑一步都问你这个窗口里最大的数是几。LeetCode上对应的是239题难度分类是困难但实际掌握了单调队列的思路后你会发现它其实是被“困难”两个字吓住了很多人核心代码也就二十来行。这篇文章我准备把这道题从暴力解法到单调队列优化从代码实现到面试追问一次性讲透适合正在刷题准备面试的朋友也适合刚学完数据结构想找实战场景的初学者。我第一次做这道题的时候其实是被“困难”标签唬住的。后来想明白了这题考察的就两件事一是你懂不懂滑动窗口这个模型二是你知不知道单调队列这种优化手段。这两个点一旦拆开整道题的骨架就露出来了。先别急着看答案我建议你按下面的思路一步步推推到哪一步卡住了再回头看我的讲解印象会深很多。1. 题目拆解先搞清楚滑动窗口最大值到底在考什么1.1 从暴力解法入手先知道基线在哪里很多人一上来就想着最优解结果自己把自己绕晕了。我个人的习惯是拿到题先写一个最直白的解法哪怕复杂度很烂至少能保证答案是对的然后再去想怎么优化。这道题的暴力解法非常直观窗口从0位置开始每次计算当前窗口范围[i, ik-1]内的最大值然后窗口右移一格。窗口一共会移动n-k1次每次扫描k个元素找最大值所以时间复杂度是O(nk)。public int[] maxSlidingWindow(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 1; j i k; j) { max Math.max(max, nums[j]); } res[i] max; } return res; }这个代码在n和k都比较小的时候是能跑的但一旦n到10万、k到5万双层循环就会慢到让人怀疑人生。面试的时候写这个版本基本等于告诉面试官“我只会暴力”。不过暴力版本的价值在于它帮我们把问题的计算瓶颈暴露出来了窗口每次只移动一格但我们在重复扫描窗口里的大部分元素明明上一次已经看过的数字这次又要重新比一遍。如果可以设计一种数据结构让窗口内的最大值能“动态”维护每次滑动只需要很小的代价就能拿到结果那性能就上去了。1.2 单调队列的核心思路为什么它高效顺着刚才的瓶颈往下想我们会希望窗口滑动的时候新元素加进来旧元素出去最大值这个信息能被增量地维护而不是全量重算。一个很自然的想法是维护一个“候选最大值”的集合。每次窗口滑动我们做两步操作第一步把窗口最左边滑出去的那个元素从集合里删掉第二步把新进入窗口的元素加进去然后集合里的最大值就是答案。问题来了用什么集合能做到新增、删除、取最大值都快堆优先队列可以做到Java的PriorityQueue删除任意元素是O(k)的整体复杂度不稳定。有没有更巧妙的办法这里有一个非常关键的观察如果窗口里有a和b两个元素a在b的左边但a的值比b小那么只要b还活着a就永远不可能是这个窗口的最大值。因为窗口是向右滑的a一定比b更早离开窗口。换句话说a是一个“永远卷不过b”的候选人留着它只会浪费时间。把这个观察用起来我们可以在窗口内维护一个从队头到队尾单调递减的队列。队列里存的都是“有可能成为窗口最大值”的元素而且它们是从大到小排好队的。队头就是当前窗口的最大值。当新元素x要入队时我们不停地把队尾那些比x小的元素弹出因为它们不可能再翻身当老大了。然后再把x放到队尾。这样队列始终保持着从大到小的顺序。这个思想就叫“单调队列”它保证了每个元素最多入队一次、出队一次平均到每次滑动代价是O(1)。2. 双端队列实现从原理到代码2.1 双端队列为什么是天然适配的数据结构单调队列这个思路确定后就要选数据结构了。它的操作特点是很明确的需要在队尾弹出元素淘汰小值、在队尾加入元素新元素入队、在队头弹出元素窗口左边界滑出、读取队头元素拿最大值。这四个操作正好对应双端队列Deque的能力。Java里可以这样声明DequeInteger deque new ArrayDeque();ArrayDeque底层是循环数组读写效率高不允放空值在这个场景下够用了。当然也可以用LinkedList也是双端队列的实现但常数上略慢一点。这里有一个细节队列里存的不是数组值本身而是元素在数组里的下标。为什么要存下标而不是值因为窗口滑动的时候我们需要知道队头元素是不是已经滑出窗口了。只有知道下标才能判断deque.peekFirst() i - k 1也就是队头元素是否已经不在当前窗口范围内。如果只存值这个判断就无法完成。这个点我在第三部分还会展开说。2.2 完整代码实现Java和Python都给你下面是我在面试中比较喜欢的写法逻辑清晰边界也容易处理。先看Java版本public int[] maxSlidingWindow(int[] nums, int k) { int n nums.length; if (n 0 || k 0) { return new int[0]; } int[] res new int[n - k 1]; DequeInteger deque new ArrayDeque(); for (int i 0; i n; i) { // 1. 弹出队头滑出窗口的元素 if (!deque.isEmpty() deque.peekFirst() i - k 1) { 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; }Python版本核心逻辑一模一样from collections import deque def maxSlidingWindow(nums, k): n len(nums) if n 0 or k 0: return [] res [] dq deque() for i in range(n): # 弹出队头滑出窗口的元素 if dq and dq[0] i - k 1: dq.popleft() # 弹出队尾所有比当前元素小的元素 while dq and nums[dq[-1]] nums[i]: dq.pop() dq.append(i) # 窗口形成后收集结果 if i k - 1: res.append(nums[dq[0]]) return res这段代码的循环里一共有四个动作顺序很重要先清理过期元素再淘汰队尾小值然后入队最后取结果。很多人写的时候会把第2步和第1步反了或者漏掉第1步就会出一些看起来很奇怪的bug稍后我在第四部分专门列几个踩坑案例。3. 核心细节与复杂度分析别只背代码要懂为什么3.1 为什么队列里存下标而不是值这个点面试官特别喜欢问。如果只存值当队头元素滑出窗口时你无法知道它到底应不应该离开更麻烦的是如果窗口里有重复值只存值会导致你根本分不清哪个值先来后到。存下标就能精确地做两个判断一是nums[i]和nums[deque.peekLast()]比较大小二是deque.peekFirst()是否小于i - k 1来判断队头是否已经越界。这里还有一个细节while循环里比较用的是还是我写的是也就是当队尾元素和当前新元素相等时把队尾元素弹出去让新元素入队。这样做对吗是对的。因为两个相等的元素下标更大的那个存活时间更长更适合作为候选最大值。把旧相等元素淘汰掉不需要额外付出任何代价还让队列里存储的元素更“新鲜”。如果写旧相等元素就会一直留在队列里但因为它和新元素值一样大、又更早离开窗口等旧元素滑出时就很尴尬等于留了一个没用的候选者。所以遇到相等值直接让新的淘汰旧的代码更干净。3.2 初始化窗口与滑动过程的统一写法很多资料的写法是分两步先把第一个窗口的k个元素处理完再开始滑动收集结果。这样写也没问题但要多写一段重复逻辑代码不够紧凑。我更喜欢上面的写法从头到尾只用一次循环在循环里用i k - 1作为“窗口是否已经形成”的判断条件。前k-1个元素的时候只做入队和维护操作不输出结果从第k-1个元素开始每轮都输出一个结果。这个统一写法可以减少代码分支也降低了漏写情况的概率。我们来手推一遍用数组[1, 3, -1, -3, 5, 3, 6, 7]k 3i0元素1队列为空入队。队列[0(1)]。i 2不输出。i1元素3队尾1比3小弹出入队1(3)。队列[1(3)]。i 2不输出。i2元素-1队尾3比-1大保留入队2(-1)。队列[1(3), 2(-1)]。窗口形成输出nums[队头]3。结果[3]。i3元素-3队头下标1仍满足 1不出队队尾-1比-3大保留入队3(-3)。队列[1(3), 2(-1), 3(-3)]。输出3。结果[3, 3]。i4元素5此时窗口范围是[2,4]队头下标1已经小于2出队然后队尾-3、-1、3全都比5小依次弹出入队4(5)。队列[4(5)]。输出5。结果[3, 3, 5]。i5元素3队头4满足 3队尾5比3大保留入队5(3)。队列[4(5), 5(3)]。输出5。结果[3, 3, 5, 5]。i6元素6队尾3、5都比6小依次弹出入队6(6)。队列[6(6)]。输出6。结果[3, 3, 5, 5, 6]。i7元素7队尾6比7小弹出入队7(7)。队列[7(7)]。输出7。结果[3, 3, 5, 5, 6, 7]。推一遍下来整个逻辑就非常直观了。你会发现队列里的元素始终保持单调递减的顺序队头永远是当前窗口最大值。3.3 复杂度推导时间复杂度上每个元素最多入队一次、出队一次出队动作可能发生在队头也可能发生在队尾但总数不会超过n次。所以整个循环的总操作次数是O(n)均摊到每次滑动就是常数时间。空间复杂度是O(k)因为队列里最多同时存k个元素有些情况下队列长度可能比k小很多比如数组严格递减时队列会一直累积到k个数组严格递增时队列始终只有1个元素但最坏情况不会超过k。对比之前暴力解法的O(nk)这是一个质的飞跃。这里我想多说一句复杂度分析的心得。很多人觉得复杂度分析就是背结论其实不是。像这道题你要想明白为什么均摊是O(1)关键就在于“每个元素只被处理两次”这个事实。这类“虽然看上去循环里有循环但每个元素进出一次”的套路在很多单调栈/单调队列题目里都会出现理解了它你以后做接雨水、柱状图最大矩形这类题也会顺手很多。4. 常见坑点与排查技巧实录4.1 边界条件相关的坑第一道坑是k比n大或者k等于0、数组为空。我刚开始写的时候没加这个判断结果在一些极端测试用例上直接数组越界。稳妥的做法是函数一进来就判空if (n 0 || k 0) { return new int[0]; }有些题里也可能出现k大于n的情况严格来说这种用例不合规但还是防御性处理一下比较好。第二个坑是队列清理过期元素的时机。我见过有人先把新元素入队然后再去清理队头这样在极端情况下会把正常元素误删。顺序必须是先判断队头是否过期再淘汰队尾小值再入队再取结果。这个顺序一旦打乱调试起来非常痛苦因为问题不是必现而是取决于具体的数组排列。第三个坑是while循环里比较的是下标还是值这个比较容易搞混。nums[deque.peekLast()]才是值deque.peekLast()是下标。如果直接拿元素值和下标比在数组元素刚好在0附近时会得到完全错误的结果。第四个坑是Java的ArrayDeque不允许存储null但这道题我们存的是下标所以不会遇到null问题。不过你要是复用了这段代码去处理别的场景被提醒一下总是好的。4.2 面试时的几个关键追问面试官在考察这道题的时候通常不会只让你把代码写出来。至少这几个问题是常问的第一个问题为什么用双端队列而不是优先队列答案是优先队列的删除操作需要先找到那个元素再删除时间复杂度是O(k)而双端队列能让所有操作都变成O(1)。面试官如果继续追问你就需要解释清楚“每个元素最多进出队列一次”的均摊代价。第二个问题如果要求输出每个窗口的最小值怎么改很简单把单调队列的单调性反过来从队头到队尾单调递增队头就是最小值。代码几乎不用变只需要把改成也就是淘汰队尾所有比当前元素大的元素。第三个问题如果数组是流式的也就是数据一个一个到达不知道总长度还能做吗可以。这就是滑动窗口限流的底层思路之一。我们不需要知道n只需要维护一个窗口起始位置left每次新元素到达时先清理小于left的队头再按同样的逻辑维护队列。这个变体和剑指offer原题是同一个核心。第四个问题这个算法和TCP流量控制里的滑动窗口是一回事吗这是新手容易混淆的地方。TCP的滑动窗口是流量控制模型目的是协调发送端和接收端的速率这里的滑动窗口是算法题里的固定窗口扫描模型。两者只是名字里都有“滑动窗口”本质上不是一回事。面试时如果你的简历里有网络相关的项目面试官可能会顺带问一句最好能分清楚。4.3 变体与扩展这道题背后藏的是一类问题滑动窗口 单调性查询。掌握了单调队列下面这些题目你都能很快想到思路求每个窗口的最小值把单调性反过来。求每个窗口的最大值和最小值之差极差同时维护两个单调队列一个递增一个递减。求满足条件的最短/最长子数组用双指针维护窗口配合单调队列求窗口内的最值。环形数组上类似的窗口问题把数组复制一份接在后面再套同样的模板。我之前在项目里还用过这个思路做实时数据的峰值检测比如采集一段传感器数据想知道每秒钟内温度的最高值和最低值就是典型的滑动窗口最值问题。这类算法不只是面试题工程里也经常派上用场。4.4 一个容易被忽视的细节用while而不是if清理队尾我见过很多初学写法是if (!deque.isEmpty() nums[deque.peekLast()] nums[i]) { deque.pollLast(); }这里用if是有问题的。因为队尾可能存在多个比当前元素小的元素必须通过while循环把它们都弹掉直到队尾元素比当前元素大为止。如果只弹一次队列的单调性就被破坏了队头有概率不是最大值。这也是为什么我强调要理解“维护单调性”这个本质而不是死记某一行代码。死记代码很容易在这种细节上出错。我在实际刷题的时候发现这类“单调队列淘汰元素”的操作和生活中的排队很像窗口里来了一个更厉害的新人那些无论从能力还是从排队顺序上都不可能被轮到的人直接走人就行留下的人都是真正有竞争力的候选者。这样一想逻辑就好记多了。如果后续想做更多扩展我建议你再做一道经典题LeetCode 239滑动窗口最大值本身以及“和至少为K的最短子数组”这道题它把前缀和和单调双端队列结合起来了属于这道题的进阶版本。等你把这两道题吃透滑动窗口这个模型在你脑子里就彻底固化了以后再遇到类似题目基本就是秒杀。
滑动窗口最大值详解：从暴力到单调队列优化
剑指offer-64这道题在我刷了三遍之后终于敢说彻底吃透了。滑动窗口最大值说白了就是给你一个数组和一个固定长度的窗口窗口从左往右滑每滑一步都问你这个窗口里最大的数是几。LeetCode上对应的是239题难度分类是困难但实际掌握了单调队列的思路后你会发现它其实是被“困难”两个字吓住了很多人核心代码也就二十来行。这篇文章我准备把这道题从暴力解法到单调队列优化从代码实现到面试追问一次性讲透适合正在刷题准备面试的朋友也适合刚学完数据结构想找实战场景的初学者。我第一次做这道题的时候其实是被“困难”标签唬住的。后来想明白了这题考察的就两件事一是你懂不懂滑动窗口这个模型二是你知不知道单调队列这种优化手段。这两个点一旦拆开整道题的骨架就露出来了。先别急着看答案我建议你按下面的思路一步步推推到哪一步卡住了再回头看我的讲解印象会深很多。1. 题目拆解先搞清楚滑动窗口最大值到底在考什么1.1 从暴力解法入手先知道基线在哪里很多人一上来就想着最优解结果自己把自己绕晕了。我个人的习惯是拿到题先写一个最直白的解法哪怕复杂度很烂至少能保证答案是对的然后再去想怎么优化。这道题的暴力解法非常直观窗口从0位置开始每次计算当前窗口范围[i, ik-1]内的最大值然后窗口右移一格。窗口一共会移动n-k1次每次扫描k个元素找最大值所以时间复杂度是O(nk)。public int[] maxSlidingWindow(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 1; j i k; j) { max Math.max(max, nums[j]); } res[i] max; } return res; }这个代码在n和k都比较小的时候是能跑的但一旦n到10万、k到5万双层循环就会慢到让人怀疑人生。面试的时候写这个版本基本等于告诉面试官“我只会暴力”。不过暴力版本的价值在于它帮我们把问题的计算瓶颈暴露出来了窗口每次只移动一格但我们在重复扫描窗口里的大部分元素明明上一次已经看过的数字这次又要重新比一遍。如果可以设计一种数据结构让窗口内的最大值能“动态”维护每次滑动只需要很小的代价就能拿到结果那性能就上去了。1.2 单调队列的核心思路为什么它高效顺着刚才的瓶颈往下想我们会希望窗口滑动的时候新元素加进来旧元素出去最大值这个信息能被增量地维护而不是全量重算。一个很自然的想法是维护一个“候选最大值”的集合。每次窗口滑动我们做两步操作第一步把窗口最左边滑出去的那个元素从集合里删掉第二步把新进入窗口的元素加进去然后集合里的最大值就是答案。问题来了用什么集合能做到新增、删除、取最大值都快堆优先队列可以做到Java的PriorityQueue删除任意元素是O(k)的整体复杂度不稳定。有没有更巧妙的办法这里有一个非常关键的观察如果窗口里有a和b两个元素a在b的左边但a的值比b小那么只要b还活着a就永远不可能是这个窗口的最大值。因为窗口是向右滑的a一定比b更早离开窗口。换句话说a是一个“永远卷不过b”的候选人留着它只会浪费时间。把这个观察用起来我们可以在窗口内维护一个从队头到队尾单调递减的队列。队列里存的都是“有可能成为窗口最大值”的元素而且它们是从大到小排好队的。队头就是当前窗口的最大值。当新元素x要入队时我们不停地把队尾那些比x小的元素弹出因为它们不可能再翻身当老大了。然后再把x放到队尾。这样队列始终保持着从大到小的顺序。这个思想就叫“单调队列”它保证了每个元素最多入队一次、出队一次平均到每次滑动代价是O(1)。2. 双端队列实现从原理到代码2.1 双端队列为什么是天然适配的数据结构单调队列这个思路确定后就要选数据结构了。它的操作特点是很明确的需要在队尾弹出元素淘汰小值、在队尾加入元素新元素入队、在队头弹出元素窗口左边界滑出、读取队头元素拿最大值。这四个操作正好对应双端队列Deque的能力。Java里可以这样声明DequeInteger deque new ArrayDeque();ArrayDeque底层是循环数组读写效率高不允放空值在这个场景下够用了。当然也可以用LinkedList也是双端队列的实现但常数上略慢一点。这里有一个细节队列里存的不是数组值本身而是元素在数组里的下标。为什么要存下标而不是值因为窗口滑动的时候我们需要知道队头元素是不是已经滑出窗口了。只有知道下标才能判断deque.peekFirst() i - k 1也就是队头元素是否已经不在当前窗口范围内。如果只存值这个判断就无法完成。这个点我在第三部分还会展开说。2.2 完整代码实现Java和Python都给你下面是我在面试中比较喜欢的写法逻辑清晰边界也容易处理。先看Java版本public int[] maxSlidingWindow(int[] nums, int k) { int n nums.length; if (n 0 || k 0) { return new int[0]; } int[] res new int[n - k 1]; DequeInteger deque new ArrayDeque(); for (int i 0; i n; i) { // 1. 弹出队头滑出窗口的元素 if (!deque.isEmpty() deque.peekFirst() i - k 1) { 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; }Python版本核心逻辑一模一样from collections import deque def maxSlidingWindow(nums, k): n len(nums) if n 0 or k 0: return [] res [] dq deque() for i in range(n): # 弹出队头滑出窗口的元素 if dq and dq[0] i - k 1: dq.popleft() # 弹出队尾所有比当前元素小的元素 while dq and nums[dq[-1]] nums[i]: dq.pop() dq.append(i) # 窗口形成后收集结果 if i k - 1: res.append(nums[dq[0]]) return res这段代码的循环里一共有四个动作顺序很重要先清理过期元素再淘汰队尾小值然后入队最后取结果。很多人写的时候会把第2步和第1步反了或者漏掉第1步就会出一些看起来很奇怪的bug稍后我在第四部分专门列几个踩坑案例。3. 核心细节与复杂度分析别只背代码要懂为什么3.1 为什么队列里存下标而不是值这个点面试官特别喜欢问。如果只存值当队头元素滑出窗口时你无法知道它到底应不应该离开更麻烦的是如果窗口里有重复值只存值会导致你根本分不清哪个值先来后到。存下标就能精确地做两个判断一是nums[i]和nums[deque.peekLast()]比较大小二是deque.peekFirst()是否小于i - k 1来判断队头是否已经越界。这里还有一个细节while循环里比较用的是还是我写的是也就是当队尾元素和当前新元素相等时把队尾元素弹出去让新元素入队。这样做对吗是对的。因为两个相等的元素下标更大的那个存活时间更长更适合作为候选最大值。把旧相等元素淘汰掉不需要额外付出任何代价还让队列里存储的元素更“新鲜”。如果写旧相等元素就会一直留在队列里但因为它和新元素值一样大、又更早离开窗口等旧元素滑出时就很尴尬等于留了一个没用的候选者。所以遇到相等值直接让新的淘汰旧的代码更干净。3.2 初始化窗口与滑动过程的统一写法很多资料的写法是分两步先把第一个窗口的k个元素处理完再开始滑动收集结果。这样写也没问题但要多写一段重复逻辑代码不够紧凑。我更喜欢上面的写法从头到尾只用一次循环在循环里用i k - 1作为“窗口是否已经形成”的判断条件。前k-1个元素的时候只做入队和维护操作不输出结果从第k-1个元素开始每轮都输出一个结果。这个统一写法可以减少代码分支也降低了漏写情况的概率。我们来手推一遍用数组[1, 3, -1, -3, 5, 3, 6, 7]k 3i0元素1队列为空入队。队列[0(1)]。i 2不输出。i1元素3队尾1比3小弹出入队1(3)。队列[1(3)]。i 2不输出。i2元素-1队尾3比-1大保留入队2(-1)。队列[1(3), 2(-1)]。窗口形成输出nums[队头]3。结果[3]。i3元素-3队头下标1仍满足 1不出队队尾-1比-3大保留入队3(-3)。队列[1(3), 2(-1), 3(-3)]。输出3。结果[3, 3]。i4元素5此时窗口范围是[2,4]队头下标1已经小于2出队然后队尾-3、-1、3全都比5小依次弹出入队4(5)。队列[4(5)]。输出5。结果[3, 3, 5]。i5元素3队头4满足 3队尾5比3大保留入队5(3)。队列[4(5), 5(3)]。输出5。结果[3, 3, 5, 5]。i6元素6队尾3、5都比6小依次弹出入队6(6)。队列[6(6)]。输出6。结果[3, 3, 5, 5, 6]。i7元素7队尾6比7小弹出入队7(7)。队列[7(7)]。输出7。结果[3, 3, 5, 5, 6, 7]。推一遍下来整个逻辑就非常直观了。你会发现队列里的元素始终保持单调递减的顺序队头永远是当前窗口最大值。3.3 复杂度推导时间复杂度上每个元素最多入队一次、出队一次出队动作可能发生在队头也可能发生在队尾但总数不会超过n次。所以整个循环的总操作次数是O(n)均摊到每次滑动就是常数时间。空间复杂度是O(k)因为队列里最多同时存k个元素有些情况下队列长度可能比k小很多比如数组严格递减时队列会一直累积到k个数组严格递增时队列始终只有1个元素但最坏情况不会超过k。对比之前暴力解法的O(nk)这是一个质的飞跃。这里我想多说一句复杂度分析的心得。很多人觉得复杂度分析就是背结论其实不是。像这道题你要想明白为什么均摊是O(1)关键就在于“每个元素只被处理两次”这个事实。这类“虽然看上去循环里有循环但每个元素进出一次”的套路在很多单调栈/单调队列题目里都会出现理解了它你以后做接雨水、柱状图最大矩形这类题也会顺手很多。4. 常见坑点与排查技巧实录4.1 边界条件相关的坑第一道坑是k比n大或者k等于0、数组为空。我刚开始写的时候没加这个判断结果在一些极端测试用例上直接数组越界。稳妥的做法是函数一进来就判空if (n 0 || k 0) { return new int[0]; }有些题里也可能出现k大于n的情况严格来说这种用例不合规但还是防御性处理一下比较好。第二个坑是队列清理过期元素的时机。我见过有人先把新元素入队然后再去清理队头这样在极端情况下会把正常元素误删。顺序必须是先判断队头是否过期再淘汰队尾小值再入队再取结果。这个顺序一旦打乱调试起来非常痛苦因为问题不是必现而是取决于具体的数组排列。第三个坑是while循环里比较的是下标还是值这个比较容易搞混。nums[deque.peekLast()]才是值deque.peekLast()是下标。如果直接拿元素值和下标比在数组元素刚好在0附近时会得到完全错误的结果。第四个坑是Java的ArrayDeque不允许存储null但这道题我们存的是下标所以不会遇到null问题。不过你要是复用了这段代码去处理别的场景被提醒一下总是好的。4.2 面试时的几个关键追问面试官在考察这道题的时候通常不会只让你把代码写出来。至少这几个问题是常问的第一个问题为什么用双端队列而不是优先队列答案是优先队列的删除操作需要先找到那个元素再删除时间复杂度是O(k)而双端队列能让所有操作都变成O(1)。面试官如果继续追问你就需要解释清楚“每个元素最多进出队列一次”的均摊代价。第二个问题如果要求输出每个窗口的最小值怎么改很简单把单调队列的单调性反过来从队头到队尾单调递增队头就是最小值。代码几乎不用变只需要把改成也就是淘汰队尾所有比当前元素大的元素。第三个问题如果数组是流式的也就是数据一个一个到达不知道总长度还能做吗可以。这就是滑动窗口限流的底层思路之一。我们不需要知道n只需要维护一个窗口起始位置left每次新元素到达时先清理小于left的队头再按同样的逻辑维护队列。这个变体和剑指offer原题是同一个核心。第四个问题这个算法和TCP流量控制里的滑动窗口是一回事吗这是新手容易混淆的地方。TCP的滑动窗口是流量控制模型目的是协调发送端和接收端的速率这里的滑动窗口是算法题里的固定窗口扫描模型。两者只是名字里都有“滑动窗口”本质上不是一回事。面试时如果你的简历里有网络相关的项目面试官可能会顺带问一句最好能分清楚。4.3 变体与扩展这道题背后藏的是一类问题滑动窗口 单调性查询。掌握了单调队列下面这些题目你都能很快想到思路求每个窗口的最小值把单调性反过来。求每个窗口的最大值和最小值之差极差同时维护两个单调队列一个递增一个递减。求满足条件的最短/最长子数组用双指针维护窗口配合单调队列求窗口内的最值。环形数组上类似的窗口问题把数组复制一份接在后面再套同样的模板。我之前在项目里还用过这个思路做实时数据的峰值检测比如采集一段传感器数据想知道每秒钟内温度的最高值和最低值就是典型的滑动窗口最值问题。这类算法不只是面试题工程里也经常派上用场。4.4 一个容易被忽视的细节用while而不是if清理队尾我见过很多初学写法是if (!deque.isEmpty() nums[deque.peekLast()] nums[i]) { deque.pollLast(); }这里用if是有问题的。因为队尾可能存在多个比当前元素小的元素必须通过while循环把它们都弹掉直到队尾元素比当前元素大为止。如果只弹一次队列的单调性就被破坏了队头有概率不是最大值。这也是为什么我强调要理解“维护单调性”这个本质而不是死记某一行代码。死记代码很容易在这种细节上出错。我在实际刷题的时候发现这类“单调队列淘汰元素”的操作和生活中的排队很像窗口里来了一个更厉害的新人那些无论从能力还是从排队顺序上都不可能被轮到的人直接走人就行留下的人都是真正有竞争力的候选者。这样一想逻辑就好记多了。如果后续想做更多扩展我建议你再做一道经典题LeetCode 239滑动窗口最大值本身以及“和至少为K的最短子数组”这道题它把前缀和和单调双端队列结合起来了属于这道题的进阶版本。等你把这两道题吃透滑动窗口这个模型在你脑子里就彻底固化了以后再遇到类似题目基本就是秒杀。