引言

大家好啊，我是前端拿破轮😁。

跟着卡哥学算法有一段时间了，通过代码随想录的学习，受益匪浅，首先向卡哥致敬🫡。

但是在学习过程中我也发现了一些问题，很多当时理解了并且AC的题目过一段时间就又忘记了，或者不能完美的写出来。根据费曼学习法，光有输入的知识掌握的是不够牢靠的，所以我决定按照代码随想录的顺序，输出自己的刷题总结和思考。同时，由于以前学习过程使用的是JavaScript,而在2025年的今天，TypeScript几乎成了必备项，所以本专题内容也将使用TypeScript，来巩固自己的TypeScript语言能力。

题目信息

滑动窗口最大值

leetcode题目链接

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

题目分析

此题要想AC并不难，只需要遍历数组，维护一个大小为k的滑动窗口，在窗口中再利用Math.max求值即可。但是时间复杂度是$O(N*K)$，其中N为数组长度，K为滑动窗口大小。

那能不能在$O(n)$的复杂度内AC呢？其实我们观察暴力解法会发现，当我们在使用Math.max时，做了很多重复的比较。当窗口只移动一位时，其实有两个元素是原来在窗口中，后来还在的。他们大小关系在第一次就已经比较出来了，但我们没有利用起来，而是又重新进行了下一次的比较。

沿着这个思路想，我们可以思考，有没有一种数据结构可以保留这个最大值的信息呢？答案就是单调队列。

其实我们在往队列中添加元素的时候，如果当前元素大于之前的元素，那么之前的元素就没有存在的必要了。因为之前的元素如果小于当前值，那么它一定不是最大值了，直接给他pop走即可。

此外，还有一个问题，就是怎么判断队列中的元素是不是还在窗口内呢？如果直接在队列中维护数组中元素的值，其实是很难判断元素是不是在窗口中的。

所以，对于本题，我们在队列中不维护数组元素本身，而是维护数组元素的下标。这样我们根据元素的下标和当前下标之间的差值便可以轻而易举地判断元素是否在窗口中了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function maxSlidingWindow(nums: number[], k: number): number[] {
    const result: number[] = [];
    const deque: number[] = []; // 单调递减队列，存索引 

    for (let i = 0; i < nums.length; i++) {
        // 移除队头不在窗口范围内的元素
        if (deque.length && deque[0] <= i - k) {
            deque.shift();
        }

        // 保证队列从头到尾对应的值都是单调递减的
        while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {
            deque.pop();
        }

        // 当前元素入队
        deque.push(i);

        // 记录窗口最大值
        if (i >= k - 1) {
            result.push(nums[deque[0]]);
        }
    }
    return result;
};

时间复杂度: $O(N)$, 只需要遍历一次数组

空间复杂度: $O(K)$, K为窗口大小

总结

本题是单调队列的典型应用，属于困难题目。在这里有三个难点：

  1. 怎么判断一个元素在不在滑动窗口内

  2. 如何找到窗口中的最大值

  3. 如何确保队列单调

对于1，我们采用了存储下标而不是直接存储值的方式，从而可以根据存储的下标和当前遍历的下标轻松判断元素在不在窗口内。

对于2和3，我们使用了单调双端队列。所谓单调，是指队列中的元素排序单调递增或递减。双端则是指既可以从队首出队，也可以从队尾出队。

好了，这篇文章就到这里啦，如果对您有所帮助，欢迎点赞,收藏,分享👍👍👍。您的认可是我更新的最大动力。由于笔者水平有限，难免有疏漏不足之处，欢迎各位大佬评论区指正。

往期推荐✨✨✨

我是前端拿破轮，关注我，一起学习前端知识，我们下期见！