【LeetCode 热题 100】239. 滑动窗口最大值——（解法一）滑动窗口+暴力解
Problem: 239. 滑动窗口最大值
题目：给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值 。
文章目录
- 整体思路
- 完整代码
- 时空复杂度
- 时间复杂度：O(N * k)
- 空间复杂度：O(k)
- 注意：暴力解会超时
整体思路
这段代码的目的是解决经典的 “滑动窗口最大值” 问题。即，在一个整数数组 nums 中，找出一个大小为 k 的滑动窗口在从左到右移动时，每个窗口内的最大值。
该算法实现了一种 模拟滑动窗口 的暴力解法。它虽然使用了双端队列（Deque）这一数据结构，但并没有发挥其在最优解法（单调队列）中的关键作用，而是仅仅将其用作一个普通的队列来存储当前窗口内的所有元素。
其核心逻辑步骤如下：
-
初始化：
- 创建一个结果数组
ans，其长度为n - k + 1，因为这正是滑动窗口的总数。 - 创建一个双端队列
win，用来存储当前滑动窗口中的所有元素。
- 创建一个结果数组
-
滑动窗口模拟：
- 算法使用一个
for循环，由right指针驱动，从左到右遍历整个nums数组。right代表窗口的右边界。 - 窗口维护：
a. 元素出队（收缩窗口）：当窗口已经形成并需要向右滑动时（即right > k - 1，意味着要加入第k+1个元素了），就从队列的头部弹出一个元素（win.pop()）。这模拟了窗口最左边的元素移出窗口的过程。
b. 元素入队（扩张窗口）：将当前right指针指向的元素nums[right]加入到队列的尾部（win.add())。 - 通过这两步，
win队列始终保持着当前滑动窗口内的所有元素。
- 算法使用一个
-
查找当前窗口最大值（暴力法）：
- 【效率瓶颈】 在每次更新窗口后，代码会进入一个内部的
for-each循环，遍历win队列中的 所有元素，以线性扫描的方式找出当前窗口的最大值max。 - 这是该算法效率不高的根本原因。
- 【效率瓶颈】 在每次更新窗口后，代码会进入一个内部的
-
记录结果：
- 当窗口首次形成（即
right >= k - 1）以及后续的每次滑动后，将上一步找到的最大值max存入结果数组ans的相应位置（ans[right - k + 1]）。
- 当窗口首次形成（即
-
返回结果：
- 遍历结束后，返回填充好的
ans数组。
- 遍历结束后，返回填充好的
总结来说，这是一个思路直接、易于理解的解法：用队列维护窗口元素，每次滑动后，重新扫描整个窗口找到最大值。
完整代码
class Solution {/*** 计算滑动窗口的最大值。* @param nums 整数数组* @param k 窗口大小* @return 包含每个窗口最大值的数组*/public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length;// 计算结果数组的长度，即滑动窗口的总数int m = n - k + 1;// ans 用于存储每个窗口的最大值int[] ans = new int[m];// win 是一个双端队列，在此实现中被用作普通队列来存储当前窗口的所有元素Deque<Integer> win = new ArrayDeque<>(k); // 初始化容量为k// right 指针作为窗口的右边界，遍历整个数组for (int right = 0; right < n; right++) {// 当窗口大小即将超过 k 时，需要从左侧移除一个元素// right > k - 1 意味着我们正要处理第 k+1 个元素（从0计数），此时窗口已满if (right > k - 1) {// win.pop() 从队列头部移除元素，模拟窗口向右滑动win.pop();}// 将当前 right 指针指向的元素加入队列尾部win.add(nums[right]);// 【效率瓶颈】// 在每次窗口更新后，暴力遍历当前窗口中的所有元素以查找最大值int max = Integer.MIN_VALUE;for (int x : win) {// 使用三元运算符更新最大值max = max > x ? max : x;}// 当窗口大小达到 k 时，开始记录结果// right >= k - 1 标志着第一个完整的窗口已经形成if (right >= k - 1) {// 计算当前窗口在结果数组 ans 中的索引ans[right - k + 1] = max;}}return ans;}
}
时空复杂度
时间复杂度：O(N * k)
- 外层循环：
for (int right = 0; right < n; right++)遍历整个输入数组nums，执行N次，其中N是nums的长度。 - 内层循环：
for (int x : win)循环遍历win队列中的所有元素。win队列的大小始终保持在k或小于k。在窗口形成后，其大小恒为k。因此，这个内层循环每次执行的操作数是 O(k)。 - 循环内部操作：队列的
pop()和add()操作的平均时间复杂度都是 O(1)。
综合分析：
算法的总时间复杂度由外层循环和内层循环的乘积决定。外层循环执行 N 次，每次内部都进行一次 O(k) 的扫描。因此，总的时间复杂度为 N * O(k) = O(N * k)。
空间复杂度：O(k)
- 主要存储开销：算法使用了一个双端队列
win来存储窗口内的元素。 - 空间大小：
win队列的大小最多为k，因为它存储的是一个大小为k的滑动窗口的元素。 - 结果数组：
ans数组的大小是N - k + 1，属于 O(N) 级别。在复杂度分析中，输出结果所占用的空间通常不计入 额外辅助空间（auxiliary space）。
综合分析：
算法所需的额外辅助空间主要由 win 队列决定。因此，其空间复杂度为 O(k)。如果把输出数组也计算在内，则总空间为 O(N)。按照标准，我们通常只分析辅助空间，即 O(k)。
注意：暴力解会超时
这个方法时间复杂度为O(N * k)，会超时。
【LeetCode 热题 100】239. 滑动窗口最大值——（解法二）滑动窗口+单调队列
【LeetCode 热题 100】239. 滑动窗口最大值——（解法三）滑动窗口+单调队列+数组