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

【LeetCode 热题 100】239. 滑动窗口最大值——（解法一）滑动窗口+暴力解

文章目录

整体思路
完整代码
时空复杂度
- 时间复杂度：O(N)
- 空间复杂度：O(k)

整体思路

这段代码旨在高效地解决 “滑动窗口最大值” 问题。与上一个 O(N*k) 的暴力解法不同，此版本采用了 单调队列（Monotonic Queue） 的核心思想，这是一种专门为此类问题设计的优化数据结构，能将时间复杂度降至线性级别。

算法的核心在于维护一个单调递减的双端队列 win。这个队列有以下几个关键特性：

存储内容：队列中存储的不是元素值，而是元素在原数组 nums 中的索引。
单调性：队列中的索引所对应的 nums 值是严格单调递减的。即 nums[win[0]] > nums[win[1]] > nums[win[2]] ...。
队首即最大值：由于队列的单调性，队首元素 win.peekFirst() 始终是当前窗口内最大值的索引。

算法的执行步骤如下：

初始化：
- 创建一个结果数组 ans。
- 创建一个双端队列 win 作为单调队列。
滑动窗口与单调队列维护：
- 算法使用 right 指针从左到右遍历 nums 数组。对于每个新元素 nums[right]：
  a. 维护单调性（队尾操作）：
  - 进入一个 while 循环，从队尾开始检查。如果队尾索引对应的元素 nums[win.peekLast()] 小于或等于当前要入队的新元素 nums[right]，则将队尾元素弹出（win.pollLast()）。
  - 这个过程会持续进行，直到队尾元素大于新元素，或者队列为空。这确保了所有比新元素小的“旧”元素都被清除，因为它们在未来的窗口中不可能成为最大值。
  - 完成清理后，将当前元素的索引 right 加入队尾（win.offerLast(right)）。
    b. 维护窗口大小（队首操作）：
  - 检查队首元素的索引 win.peekFirst() 是否已经滑出当前窗口的左边界。窗口的左边界是 right - k + 1。如果队首索引小于这个边界（等价于 right - win.peekFirst() + 1 > k），说明队首元素已过期，需要从队首弹出（win.pollFirst()）。
    c. 记录结果：
  - 当窗口形成后（right >= k - 1），根据单调队列的性质，此时的队首元素 win.peekFirst() 就是当前窗口最大值的索引。
  - 将 nums[win.peekFirst()] 存入结果数组 ans 的相应位置。
返回结果：
- 遍历结束后，返回 ans 数组。

通过这种方式，每个元素最多入队一次、出队一次，使得在整个过程中找到所有窗口最大值的均摊时间复杂度为 O(1)，从而实现了整体的线性时间复杂度。

完整代码

class Solution {/*** 计算滑动窗口的最大值（优化版）。* @param nums 整数数组* @param k 窗口大小* @return 包含每个窗口最大值的数组*/public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length;// 计算结果数组的长度int m = n - k + 1;int[] ans = new int[m];// win: 一个双端队列，用作单调队列，存储元素的索引。// 队列中的索引对应的 nums 值保持单调递减。Deque<Integer> win = new ArrayDeque<>();// right 指针作为窗口的右边界，遍历整个数组for (int right = 0; right < n; right++) {// 步骤 1: 维护队列的单调递减性// 当队列不为空，且队尾索引对应的元素小于或等于当前元素时，// 将队尾元素弹出。因为这个较小的元素在未来不可能成为最大值。while (!win.isEmpty() && nums[win.peekLast()] <= nums[right]) {win.pollLast();}// 将当前元素的索引加入队尾win.offerLast(right);// 步骤 2: 维护窗口的有效范围// 检查队首元素的索引是否已经滑出窗口左边界。// 窗口的左边界是 right - k + 1。如果队首索引小于它，则说明已过期。// (right - win.peekFirst() + 1) 是队首元素和当前元素构成的窗口大小。if (right - win.peekFirst() + 1 > k) {// 弹出过期的队首元素win.pollFirst();}// 步骤 3: 记录结果// 当窗口大小达到 k 时（即 right 遍历到第 k-1 个元素时），开始记录最大值if (right >= k - 1) {// 由于队列的单调性，队首元素始终是当前窗口内最大值的索引ans[right - k + 1] = nums[win.peekFirst()];}}return ans;}
}

时空复杂度

时间复杂度：O(N)

循环：代码的主体是一个 for 循环，它遍历 nums 数组一次，执行 N 次。
队列操作：
- while 循环中的 win.pollLast() 和 if 判断中的 win.pollFirst() 操作看起来可能导致时间复杂度升高。
- 然而，每个元素的索引最多只会入队一次和出队一次。
- offerLast 将每个索引 0 到 N-1 各压入一次，总共 N 次。
- pollLast 和 pollFirst 共同将这些索引弹出，每个索引最多被弹出一次。
- 因此，所有队列操作的总次数是 O(N) 级别的。将这些操作的成本均摊到 N 次外层循环中，每次循环的均摊时间复杂度为 O(1)。

综合分析：
算法由 N 次均摊时间复杂度为 O(1) 的操作组成。因此，总的时间复杂度是 O(N)。

空间复杂度：O(k)

主要存储开销：算法使用了一个双端队列 win 来存储索引。
空间大小：队列 win 中存储的是当前有效窗口内的候选最大值的索引。在任何时刻，队列的长度都不会超过窗口大小 k。例如，如果输入数组是严格递减的，如 [5, 4, 3, 2, 1] 且 k=3，队列会存储 [i, i+1, i+2] 三个索引。因此，队列的最大空间占用为 O(k)。
结果数组：ans 数组的空间为 O(N)，但不计入额外辅助空间。