力扣题目链接此时我们需要一个队列这个队列呢放进去窗口里的元素然后随着窗口的移动队列也一进一出每次移动之后队列告诉我们里面的最大值是什么。第一层暴力法为什么不行你的想法你说的“直接比较每k个数字里最大的”叫暴力滑动。假设数组长度n100000窗口大小k50000。每滑动一次你就要比较 50000 次一共要滑动 50001 次。总计算量是 25亿次绝对超时。第二层单调队列到底在干嘛核心思想单调队列不是在“找最大值”而是在维护一个“最大值候选人”的名单并且按出场顺序排好队。关键洞察当窗口滑动时一个新元素进来了。如果这个新元素比队列里末尾的某些旧元素还大那么那些旧元素就永远不可能成为最大值了因为它们比新元素小而且还比新元素先过期。所以直接把那些没用的旧元素从队尾踢出去。这就是“单调递减队列”名字的由来——队列里从头到尾数值越来越小。第三层为什么不需要精确弹出“被移除的那个元素”解决你的最大疑问你问“已经排序之后的队列怎么能把窗口要移除的元素弹出呢”答案是我们根本不关心它是不是在队列里我们只在它“恰好是队首”时才弹出它。请看下面这个活生生的例子你就全明白了数组[5, 3, 4, 1]窗口k3。窗口 [5, 3, 4]5 进队[5]3 进队[5, 3]比5小留着备用4 进队发现队尾的3比4小把3踢掉因为3没4大还比4先过期永无出头之日。队里变成[5, 4]。最大值 队首5。窗口滑动移除 5加入 1关键操作要移除的正是5。此时一看队首正好是5把它弹出队列变成[4]。加入 1比4小留在队尾[4, 1]。最大值 队首4。完美如果移除的元素不在队首呢比如窗口里是[4, 1, 2]队里是[4, 2]1早就被2踢掉了。当窗口移除4时队首弹出4剩下[2]。当窗口要移除1时因为 1 早就不在队列里了所以队列什么都不用做。因为 1 根本不可能是最大值我们根本不需要关心它何时被移除。这个操作让每个元素最多进出队列一次总时间直接从O(n*k)降为O(n)。例如 数组[1, 3, -1, -3, 5, 3, 6, 7]窗口大小k 3。队列里存的是下标方便判断过期为了你看得懂我写成值(下标)。步骤当前元素 (i)1. 清理过期队首下标 i-2 就弹出2. 清理弱者队尾值 新值就弹出3. 入队后队列状态4. 当前窗口最大值队首值11 (i0)窗口未满无需过期队空无人可弹[ 1(0) ]窗口未满不输出23 (i1)窗口未满无需过期队尾 1 3弹出1[ 3(1) ]窗口未满不输出3-1 (i2)窗口满了但队首下标1 0未过期队尾 3 -1否3大于-1[ 3(1), -1(2) ]输出 3✅4-3 (i3)窗口范围 [1,3]队首1未过期队尾 -1 -3否[ 3(1), -1(2), -3(3) ]输出 3✅55 (i4)窗口范围 [2,4]队首下标1 2过期弹出3队尾 -35弹-15弹35弹[ 5(4) ]输出 5✅63 (i5)窗口范围 [3,5]队首4未过期队尾 5 3否[ 5(4), 3(5) ]输出 5✅76 (i6)窗口范围 [4,6]队首4未过期队尾 36弹56弹[ 6(6) ]输出 6✅87 (i7)窗口范围 [5,7]队首6未过期队尾 67弹[ 7(7) ]输出 7✅一、我们到底在维护什么先看数据结构我们用一个双端队列deque里面只存数组下标不存数值。队列的绝对规则铁律从队首到队尾这些下标对应的数值必须严格递减。例如队首是10队尾是3中间是7即 10 7 3二、每次窗口移动只做这三步死记硬背假设当前遍历到下标i窗口范围是[i - k 1, i]。第1步清理过期如果队首的下标小于i - k 1即这个下标已经不在当前窗口里了就把队首从左边弹出去。第2步清理弱者只要队尾对应的数值小于等于nums[i]新来的数就把队尾从右边弹出去。因为新来的数比你大还比你晚过期你永远没机会当最大值了例如1 3 [-1 -3 5] 3 6 7第3步新王入队把当前下标i从队尾放进去。做完这三步队首下标对应的数值就是当前窗口的最大值。代码还没写。