yicong@algo: ~/code/04-substring/0239-sliding-window-maximum.cpp

yicong@algo:~/code/04-substring$ cat 0239-sliding-window-maximum.cpp

239. 滑动窗口最大值

困难 子串 题目 ↗ 源码 ↗

// 思路

难点不在"找最大值",而在"最大值滑出窗口之后怎么办"。 如果只记录当前最大值,它一走就没有第二大的信息了,只能重扫窗口 → O(n·k),超时。 所以要维护的不是"一个数",而是"一组还有可能成为最大值的候选"。 关键观察:如果 j < i 且 nums[j] <= nums[i],那么 j 永远不可能再成为任何窗口的最大值。 因为 i 更靠右(活得更久)、又更大(更有竞争力),任何包含 j 的未来窗口必然也包含 i。 所以 j 可以直接扔掉。 顺着这条推理,队列里剩下的元素天然满足「下标递增、值递减」,也就是单调队列: 队头 = 当前窗口的最大值 队尾 = 最新进来的元素 每来一个元素做三件事(对应题目给的 3 条提示): 1. 新元素进队,把队尾所有 <= 它的弹掉(提示 3:去除冗余元素) 2. 队头如果已经滑出窗口,弹掉 3. 窗口长度达到 k 之后,队头就是答案 队列里存的是下标,不是值——因为要靠下标判断"有没有滑出窗口"。 提示 2 说"队列大小不必与窗口大小相同"就是这个意思: 冗余元素都被弹掉了,队列长度一般远小于 k。

// 时间复杂度

O(n)。每个下标最多进队一次、出队一次,while 总共执行 O(n) 次。

// 空间复杂度

O(k)。队列里最多同时存 k 个下标。

// 易错点

1. 队列存下标而不是值。存值就没法判断是否滑出窗口。 2. 进队时要 while 弹队尾,不能只弹一个 —— 新元素可能一口气淘汰掉好几个。 3. 出队时用 if 就够,不用 while:每次 right 只右移一格,最多只有一个下标过期。 4. 弹队尾的条件是 nums[dq.back()] <= nums[right],必须是 <=。 写成 < 会让相等的元素堆积,队列变长,丢掉 O(k) 的空间保证。 5. 取答案要放在最后,并且要等 right >= k-1 才能取,否则窗口还没填满。 6. 每次访问 dq.front() / dq.back() 之前都要先判空。

// 面试口述要点

1. 先说朴素做法:每步重扫窗口 O(n·k),瓶颈在"最大值滑出后要重新找"; 2. 引出候选集合:更小且更早的元素永远没用,可以永久丢弃; 3. 于是队列保持"下标递增、值递减",队头就是最大值,O(1) 取; 4. 三步操作:弹队尾、弹队头、取队头,每个下标进出各一次,总共 O(n)。

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        deque<int> dq;                               // 存下标,对应的值从队头到队尾递减

        for (int right = 0; right < (int)nums.size(); right++) {
            // ---------- 第 1 步:新元素进队 ----------
            // 把队尾所有"值 <= 新元素"的下标弹掉:
            // 它们比新元素小,又比新元素早退出窗口,所以永远不可能再当最大值了
            while (!dq.empty() && nums[dq.back()] <= nums[right]) {
                dq.pop_back();
            }
            dq.push_back(right);

            // ---------- 第 2 步:弹掉已经滑出窗口的队头 ----------
            // 窗口是 [right-k+1, right],下标 <= right-k 的都已经出去了
            // 这里用 if 就够了:上一轮结束时的队列里,所有下标都 >= right-k,
            // 所以本轮最多只有 right-k 这一个下标会过期
            if (dq.front() <= right - k) {
                dq.pop_front();
            }

            // ---------- 第 3 步:窗口填满之后,队头就是当前窗口的最大值 ----------
            if (right >= k - 1) {
                ans.push_back(nums[dq.front()]);
            }
        }
        return ans;
    }
};

// 本地测试:输入 n k,然后 n 个整数;输出每个滑动窗口的最大值
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    if (!(cin >> n >> k)) return 0;
    vector<int> nums(n);
    for (int& x : nums) cin >> x;

    vector<int> ans = Solution().maxSlidingWindow(nums, k);
    if (ans.empty()) {
        cout << "none\n";
    } else {
        for (size_t i = 0; i < ans.size(); ++i)
            cout << ans[i] << (i + 1 == ans.size() ? '\n' : ' ');
    }
    return 0;
}