滑动窗口最大值 图解题解

这道题真正在问什么

给数组 nums 和窗口大小 k，一个长度固定为 k 的窗口从最左滑到最右，要求输出每个位置上窗口内的最大值，组成结果数组。比如 nums = [1,3,-1,-3,5,3,6,7]、窗口大小取 3，答案是 [3,3,5,5,6,7]。难点在规模：窗口有 n - k + 1 个，如果每个窗口都独立找一遍最大值，重复劳动会非常可观。

为什么暴力 O(nk) 不够，堆也不完美

逐窗口扫描是 O(nk)，n 和 k 都到十万量级时直接超时。改用大顶堆能把取最大值降到 O(log n)，但堆删不掉「已经滑出窗口的旧元素」，只能懒删除——取堆顶时反复检查它是否还在窗口内，整体 O(n log n)，且实现别扭。

真正的突破口是一个淘汰观察：如果一个数比它右边的某个新来的数还小，那它这辈子都当不了窗口最大值了——新数比它大、还比它晚离开窗口，任何同时容纳两者的窗口里，最大值轮不到它。这样的数可以当场永久扔掉，根本不必留着比较。

单调队列的不变量是什么

把上面的淘汰规则落成数据结构，就是单调队列（用双端队列实现）：队列里存下标，保持这些下标对应的值从队头到队尾严格递减。每个新数 v 入队前，先把队尾所有值小于 v 的下标弹掉——它们正是被 v 永久淘汰的数——然后 v 的下标入队尾，递减性自动延续。

队列里存下标而不是存值，是为了回答「队头还在不在窗口里」：窗口右端走到 r 时，左边界是 r - k + 1，若队头下标小于等于 r - k，说明它已滑出窗口，从队头弹掉。两条规则各管一头：队尾弹「被淘汰的」，队头弹「过期的」，剩下的队头就永远是当前窗口的最大值。

为什么队头一定是窗口最大值

可以这样论证：窗口内任何一个数，要么还留在队列里，要么曾被某个更大且更靠右的数弹掉过——被弹掉的数一定不是最大值，因为弹它的那个数就在同一窗口里且比它大。所以窗口最大值必然还在队列中；而队列按值递减、队头经过过期检查后又保证在窗口内，故队头就是答案。窗口每凑满 k 个（r >= k - 1 起），把队头对应的值记入结果即可。

一个容易写错的细节：弹队尾的条件是「严格小于新值」。如果把相等的也弹掉，遇到重复的最大值时会过早删掉一个仍在窗口内的有效下标，等旧的那个滑出窗口后就无人接班了。

复杂度怎么算，边界在哪里

时间 O(n)：虽然循环体里嵌着弹队尾的 while，但每个下标一生至多入队一次、出队一次，所有弹出加起来不超过 n 次，均摊每步 O(1)。空间 O(k)：队列里的下标全部落在同一个窗口内，规模不超过 k。

边界上注意两点：窗口大小为 1 时每个窗口就是元素自身，算法退化为原样输出，逻辑无需特判；数组全递减时任何数都弹不掉别人，队列涨到 k 长、靠队头过期出队维持规模，这也是空间上界取到 O(k) 的情形。

Python

from collections import deque
def maxSlidingWindow(nums, k):
    dq, ans = deque(), []          # dq 存下标，值单调递减
    for r, v in enumerate(nums):
        while dq and nums[dq[-1]] < v:  # 队尾弹掉更小的
            dq.pop()
        dq.append(r)
        if dq[0] <= r - k:          # 队头滑出窗口
            dq.popleft()
        if r >= k - 1:              # 窗口凑满
            ans.append(nums[dq[0]])
    return ans

C++

vector<int> maxSlidingWindow(vector<int>& nums, int k){
    deque<int> dq; vector<int> ans;
    for (int r = 0; r < nums.size(); r++) {
        while (!dq.empty() && nums[dq.back()] < nums[r])
            dq.pop_back();
        dq.push_back(r);
        if (dq.front() <= r - k) dq.pop_front();
        if (r >= k - 1) ans.push_back(nums[dq.front()]);
    }
    return ans;
}

Java

public int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> dq = new ArrayDeque<>();
    int[] ans = new int[nums.length - k + 1]; int t = 0;
    for (int r = 0; r < nums.length; r++) {
        while (!dq.isEmpty() && nums[dq.peekLast()] < nums[r])
            dq.pollLast();
        dq.offerLast(r);
        if (dq.peekFirst() <= r - k) dq.pollFirst();
        if (r >= k - 1) ans[t++] = nums[dq.peekFirst()];
    }
    return ans;
}