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;
}