LC239　滑动窗口最大值¶

困难通过率 50.3%python3核心代码模式子串样例通过牛客 AC队列数组滑动窗口单调队列堆（优先队列）区间最值查询

讲解章节：单调队列

一句话

单调队列存下标，队首恒为当前窗口的最大值所在位置。

解题思路¶

这题考什么¶

窗口宽度固定为 k，每滑一格要报一次窗口内的最大值。每次现扫一遍是 O((n - k + 1) * k)，n = 1e5、k 取 5e4 时约 2.5e9 次比较，不可行。堆（优先队列）能做到 O(n log n)，但堆里会残留已经滑出窗口的元素，得靠「懒删除」——取堆顶时反复检查下标是否过期。

单调队列（monotonic queue，一个双端队列，里面的元素按值单调递减）把它压到 O(n)。核心是一条淘汰规则：

若 i < j 且 nums[i] <= nums[j]，那么 nums[i] 永远没有机会当最大值了。
因为任何还包含 i 的窗口必然也包含 j（窗口是连续的、右端只增），
而 j 上的值不比它小。

于是维护一个下标序列 q，保证 nums[q[0]] > nums[q[1]] > … 单调递减：新元素 nums[r] 进队前，把队尾所有值不大于它的下标全部弹掉（它们已被淘汰），再把 r 追加到队尾。队首自然就是窗口里的最大值。见单调队列。

队列里存的是下标而不是值，这是整题的关键设计。窗口左端每步右移，需要判断「当前的最大值是不是已经滑出窗口了」——只有下标才能回答这个问题，存值的话根本无从判断队首那个数来自哪个位置。有了下标，出窗判据就是一行 q[0] < right - k + 1。

每个下标最多入队一次、出队一次，总操作 2n 次，所以是 O(n) 而不是 O(n k)。

实现上用普通 list 加一个 head 下标当队列：真正的双端队列从头部弹是 O(1)，而 list.pop(0) 是 O(n)（后面元素整体前移），n = 1e5 时会退化成 O(n^2)。 head 只往前挪、不真的删元素，从头部出队也就变成了 O(1)。

数据规模与复杂度¶

1 <= n <= 1e5，-1e4 <= nums[i] <= 1e4，1 <= k <= n。时间 O(n)：每个下标入队出队各一次；空间 O(n)—— 队列最坏装下全部下标（数组严格递减时谁也淘汰不掉谁）。暴力每窗口重扫是 O(n k)，最坏 2.5e9 次比较，Python 下没有可能。

坑在哪¶

队列存下标，不存值。存值就没法判断队首是否已滑出窗口，那条 q[head] < right - k + 1 的检查根本写不出来，最大值会一直沿用早已离开窗口的旧元素。
淘汰队尾用的是 nums[q[-1]] <= nums[right]，等号要带上。相等时把旧的弹掉是安全的：旧下标更靠左，会更早出窗，留着只是浪费。不带等号也不会错，但队列会变长，且相等元素的处理要额外小心。
出窗判据的下标偏移要算准：右端为 right 的窗口，左端是 right - k + 1，所以队首下标小于 right - k + 1 才算过期。写成 right - k 会把仍在窗口里的最左元素误踢，写成 right - k + 2 则会漏掉一个已过期的。
记录答案的时机是 right >= k - 1，也就是窗口刚好填满之后。从 right = 0 就开始记，会多吐 k - 1 个由不完整窗口算出的值。
三件事的顺序是「先弹队尾、再入队、再弹过期队首、最后取答案」。若把「弹过期队首」放到入队之前，right 这一步新加入的元素还没进队，队列可能被清空，取队首会越界。
不用 list.pop(0) 从头部出队：那是 O(n) 的整体前移， n = 1e5 时整体退化成 O(n^2)。这里改用 head 指针只前移不删元素。
严格比对：每个窗口的最大值唯一，输出顺序也由窗口位置定死，没有多解。

样例复核¶

nums = [1, 3, -1, -3, 5, 3, 6, 7]，k = 3，期望 [3, 3, 5, 5, 6, 7]。队列内容以「下标(值)」表示：

r=0 值1   队空 -> 入队      q = [0(1)]                      窗口未满
r=1 值3   1 <= 3 弹掉 0     q = [1(3)]                      窗口未满
r=2 值-1  -1 < 3 直接入     q = [1(3), 2(-1)]   左端 0，队首 1 有效 -> 3
r=3 值-3  直接入            q = [1(3), 2(-1), 3(-3)]  左端 1 -> 3
r=4 值5   弹 3(-3)、2(-1)、1(3) 后入   q = [4(5)]   左端 2 -> 5
r=5 值3   直接入            q = [4(5), 5(3)]    左端 3 -> 5
r=6 值6   弹 5(3)、4(5) 后入 q = [6(6)]          左端 4 -> 6
r=7 值7   弹 6(6) 后入      q = [7(7)]          左端 5 -> 7

输出 [3, 3, 5, 5, 6, 7]，与样例一致。注意 r=4 那步：若队列存的是值而不是下标，弹完之后无从知道 5 来自下标 4，后续窗口左端越过它时也就无法判断该不该踢掉。

参考实现¶

solutions/leetcode/LC239/sol.py
from typing import List, Optional


class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        # 单调队列：存**下标**，对应的值从队首到队尾严格递减。
        # 存下标而非值，是为了能判断队首是否已经滑出窗口
        q = []
        # head 是队首在 q 里的位置。用指针前移代替 list.pop(0)——
        # pop(0) 要把后面元素整体前移，是 O(n)，会让整体退化成 O(n^2)
        head = 0
        ans = []
        for right in range(n):
            # 弹队尾：值不大于新元素的下标都已被淘汰——它们更靠左（更早出窗），
            # 值又不更大，任何还包含它们的窗口都包含 right，永远轮不到它们当最大值。
            # 等号要带上：相等时留旧的没有任何好处
            while head < len(q) and nums[q[-1]] <= nums[right]:
                q.pop()
            q.append(right)
            # 弹过期队首：右端为 right 的窗口，左端是 right - k + 1，
            # 队首下标比它还小就说明已经滑出窗口。这一步必须放在入队**之后**，
            # 否则队列可能被清空，下面取队首会越界
            if q[head] < right - k + 1:
                head += 1
            # 窗口填满（下标凑够 k 个，即 right >= k - 1）之后才开始记录，
            # 否则会多吐 k - 1 个不完整窗口的值
            if right >= k - 1:
                ans.append(nums[q[head]])
        return ans

LC239 滑动窗口最大值¶