Problem: 239. 滑动窗口最大值
题目：给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值 。

整体思路

这段代码的目的是解决经典的 “滑动窗口最大值” 问题。即，在一个整数数组 nums 中，找出一个大小为 k 的滑动窗口在从左到右移动时，每个窗口内的最大值。

该算法实现了一种 模拟滑动窗口 的暴力解法。它虽然使用了双端队列（Deque）这一数据结构，但并没有发挥其在最优解法（单调队列）中的关键作用，而是仅仅将其用作一个普通的队列来存储当前窗口内的所有元素。

其核心逻辑步骤如下：

1. 初始化：

   • 创建一个结果数组 ans，其长度为 n - k + 1，因为这正是滑动窗口的总数。
   • 创建一个双端队列 win，用来存储当前滑动窗口中的所有元素。

2. 滑动窗口模拟：

   • 算法使用一个 for 循环，由 right 指针驱动，从左到右遍历整个 nums 数组。right 代表窗口的右边界。
   • 窗口维护：
     a. 元素出队（收缩窗口）：当窗口已经形成并需要向右滑动时（即 right > k - 1，意味着要加入第 k+1 个元素了），就从队列的头部弹出一个元素（win.pop()）。这模拟了窗口最左边的元素移出窗口的过程。
     b. 元素入队（扩张窗口）：将当前 right 指针指向的元素 nums[right] 加入到队列的尾部（win.add())。
   • 通过这两步，win 队列始终保持着当前滑动窗口内的所有元素。

3. 查找当前窗口最大值（暴力法）：

   • 【效率瓶颈】 在每次更新窗口后，代码会进入一个内部的 for-each 循环，遍历 win 队列中的 所有元素，以线性扫描的方式找出当前窗口的最大值 max。
   • 这是该算法效率不高的根本原因。

4. 记录结果：

   • 当窗口首次形成（即 right >= k - 1）以及后续的每次滑动后，将上一步找到的最大值 max 存入结果数组 ans 的相应位置（ans[right - k + 1]）。

5. 返回结果：

   • 遍历结束后，返回填充好的 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)

1. 外层循环：for (int right = 0; right < n; right++) 遍历整个输入数组 nums，执行 N 次，其中 N 是 nums 的长度。
2. 内层循环：for (int x : win) 循环遍历 win 队列中的所有元素。win 队列的大小始终保持在 k 或小于 k。在窗口形成后，其大小恒为 k。因此，这个内层循环每次执行的操作数是 O(k)。
3. 循环内部操作：队列的 pop() 和 add() 操作的平均时间复杂度都是 O(1)。

综合分析：
算法的总时间复杂度由外层循环和内层循环的乘积决定。外层循环执行 N 次，每次内部都进行一次 O(k) 的扫描。因此，总的时间复杂度为 N * O(k) = O(N * k)。

空间复杂度：O(k)

1. 主要存储开销：算法使用了一个双端队列 win 来存储窗口内的元素。
2. 空间大小：win 队列的大小最多为 k，因为它存储的是一个大小为 k 的滑动窗口的元素。
3. 结果数组：ans 数组的大小是 N - k + 1，属于 O(N) 级别。在复杂度分析中，输出结果所占用的空间通常不计入 额外辅助空间（auxiliary space）。

综合分析：
算法所需的额外辅助空间主要由 win 队列决定。因此，其空间复杂度为 O(k)。如果把输出数组也计算在内，则总空间为 O(N)。按照标准，我们通常只分析辅助空间，即 O(k)。

注意：暴力解会超时

这个方法时间复杂度为O(N * k)，会超时。

【LeetCode 热题 100】239. 滑动窗口最大值——（解法二）滑动窗口+单调队列

【LeetCode 热题 100】239. 滑动窗口最大值——（解法三）滑动窗口+单调队列+数组