困难LeetCode 239可逐步演示引导学习
滑动窗口最大值
单调队列：窗口里的候选项
维护一个下标单调递减的队列：队头始终是当前窗口最大值的下标；窗口右移时，从队尾淘汰比新元素小的值，从队头淘汰已经滑出窗口的下标。
时间复杂度 O(n)空间复杂度 O(k)
题单：面试热题
题目描述
给定一个整数数组 nums 和窗口大小 k，窗口从数组最左端开始，每次向右移动一位。返回每个窗口内的最大值。
学习目标
能说清为什么可以淘汰较小元素，写出 O(n) 的单调队列实现，并正确处理窗口边界。
已完成 0 / 5 阶段
诊断
暴力扫描哪里慢
每个窗口都重新找最大值，时间复杂度是多少？哪些比较是重复的？
建议先完成当前阶段（提示 / 检查 / 自评），再进入下一步；也可以直接跳过。
解题思路
核心思想
维护一个下标单调递减的队列：队头始终是当前窗口最大值的下标；窗口右移时，从队尾淘汰比新元素小的值，从队头淘汰已经滑出窗口的下标。
为什么需要它
每个窗口都重新找最大值是 O(n·k)。窗口右移只增加一个元素、移除一个元素，很多旧元素已经不可能再成为最大值；单调队列把这些没希望的候选项提前删掉。
第一反应：直觉方案
枚举每个窗口，再线性扫描 k 个元素找最大值，正确但最坏 O(n·k)。
关键洞察
关键洞察：如果新来的数比队尾大，队尾那个数在它离开窗口之前都不可能成为最大值，因为后面这个更大的数会一直和它同处一个窗口。于是可以从队尾直接淘汰它。队列里留下的下标对应值从大到小排列，队头就是答案。
时间复杂度 O(n)空间复杂度 O(k)
易错点
- 队列存下标而不是值，才能判断队头是否已经滑出窗口。
- 先淘汰过期队头，再淘汰比新元素小的队尾，最后放入新下标。
- 结果只在窗口长度达到 k 后记录；k=1 时每个元素都是答案。
逐步演示
参考代码
1function maxSlidingWindow(nums, k) {
2 const result = [];
3 const deque = [];
4
5 for (let i = 0; i < nums.length; i++) {
6 while (deque.length > 0 && deque[0] <= i - k) {
7 deque.shift();
8 }
9 while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) {
10 deque.pop();
11 }
12 deque.push(i);
13 if (i >= k - 1) {
14 result.push(nums[deque[0]]);
15 }
16 }
17
18 return result;
19}
效果图
当前场景
双端队列
队头空队尾
第 1 / 24 步