BM45　滑动窗口的最大值¶

较难通过率 27.38%python3核心代码模式样例通过牛客 AC队列堆双指针

牛客原题　源码

讲解章节：单调队列

一句话

单调递减双端队列存下标，队首恒为当前窗口最大值，总代价 O(n)。

解题思路¶

这题考什么¶

维护一个下标递增、对应值单调递减的双端队列（单调队列）：

新元素 num[i] 进队前，把队尾所有 <= num[i] 的下标弹掉—— 它们既比 num[i] 小、又比 num[i] 先滑出窗口，此后永远轮不到它们当最大值；
队首下标若 <= i - size 说明已滑出窗口，从队首弹掉；
队首下标对应的值就是当前窗口的最大值。

队列里存的是下标而不是值：判断队首有没有过期，靠的是「它的位置离 i 多远」，只存值就无从判断，队首元素滑出窗口后仍会被当成最大值报出去。

循环不变量：每一步结束时，队列里的下标都落在当前窗口内，且对应值严格从大到小。每个下标最多进队一次、出队一次，总操作数是 O(n)。单调队列的模板与推导见单调队列。

数据规模与复杂度¶

1 <= n <= 10000，0 <= size <= 10000，|val| <= 10000，时限「其他语言 2 秒」。暴力对每个窗口取一次 max 是 O(nsize)，n = size = 1e4 时约 1e8 次比较，Python 上必然超时；写成 max(num[i:i+size]) 只是把循环挪进 C 层，复杂度没变，还多出 n 次切片拷贝，并不是*优化。单调队列时间 O(n)、空间 O(n)，正好对上题面要求。

坑在哪¶

队列存下标不存值。存值的写法在「队首刚好滑出窗口」时无法识别，例如 [4,3,2,1] 取 size=2，走到 i=2 时队首那个 4 早该出局。
size == 0 与 size > n 必须先挡掉：题面写明「窗口大于数组长度或窗口长度为 0 的时候返回空」，示例 3 给的就是 [1,2,3,4],5。不挡的话 size=0 时 i >= size-1 恒成立，每一步都会吐出一个答案；size>n 时同样会吐出短窗口的结果。
过期判断写 q[0] <= i - size。写成 < 会多留一个下标，窗口实际变成 size+1 长，最大值偏大；样例 2 的 size=5 正好能把这个错误暴露出来。
答案从 i >= size - 1 才开始记：前面的窗口还没填满，此时队首只是前缀最大值。
队尾弹出用 <=（相等也弹）而不是 <：求最大值时更早的等值下标留着也没用，弹掉能让队列更短。两种写法答案相同，但求「窗口最小值」等变体时对称条件要跟着改。

样例复核¶

[2,3,4,2,6,2,5,1] 取 size=3。i=2 时队列（下标）为 [2]，输出 num[2]=4； i=3 时 2 不大于 4，队列 [2,3]，输出 4；i=4 时 6 把队尾全部弹空，队列 [4]，输出 6；随后两步 6 仍在窗口内，输出 6、6；i=7 时下标 4 过期，队首变成 5，输出 num[6]=5。合计 [4,4,6,6,6,5]，与样例一致。

参考实现¶

solutions/nowcoder/BM45/sol.py
from collections import deque
from typing import List, Optional


class Solution:
    def maxInWindows(self, num: List[int], size: int) -> List[int]:
        n = len(num)
        if size <= 0 or size > n:            # 题目规定：窗口为 0 或超过数组长度返回空
            return []
        # 存下标而非值：队首是否已滑出窗口，只能靠下标与当前 i 的距离判断
        q = deque()                          # 存下标，对应的值单调递减
        res: List[int] = []
        for i in range(n):
            x = num[i]
            # 队尾比新元素小的下标，既更小又更早过期，可以永久丢弃
            while q and num[q[-1]] <= x:
                q.pop()
            q.append(i)
            # 窗口每次只右移一格，最多只有一个下标刚好过期，用 if 足够
            if q[0] <= i - size:
                q.popleft()
            # 前 size-1 步窗口尚未填满，从 i = size-1 起每前进一格恰好产出一个答案
            if i >= size - 1:
                res.append(num[q[0]])
        return res

BM45 滑动窗口的最大值¶