滑动窗口最大值：如何以 O(n) 求每个窗口的最大值？

直接回答：用单调递减双端队列。队列里存下标，维护规则：新元素入队前，从队尾弹出所有比它小的元素（它们再也不可能成为最大值）；队首元素滑出窗口范围时弹出。这样队首始终是当前窗口最大值的下标，每个元素恰好进出队一次，总时间 O(n)、空间 O(k)。

展开解析：核心洞察是「后来者居上」：若 a 在 b 之前且 a < b，那么 a 在任何同时包含两者的窗口里都不可能是最大值，可以永久丢弃——队列只需保留单调递减的候选链。这就是单调队列与单调栈的共同思想（栈处理一维方向、队列处理带窗口过期）。对比朴素 O(nk) 和堆 O(n log k)：堆不能高效删除滑出窗口的任意元素，需要懒删除技巧。变体与追问：滑动窗口最小值（改比较方向）、两者组合可解「窗口最大值减最小值不超过 limit 的最长子数组」；单调栈族题还有每日温度、下一个更大元素（环形数组用取模扫两遍）。

示例：

from collections import deque

def max_sliding_window(nums, k):
    q = deque()
    res = []
    for i, x in enumerate(nums):
        while q and nums[q[-1]] < x:
            q.pop()                    # 比新元素小的永无出头之日
        q.append(i)
        if q[0] <= i - k:
            q.popleft()                # 滑出窗口
        if i >= k - 1:
            res.append(nums[q[0]])
    return res