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

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

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

整体思路

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

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

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

算法的执行步骤如下：

1. 初始化：

   • 创建一个结果数组 ans。
   • 创建一个双端队列 win 作为单调队列。

2. 滑动窗口与单调队列维护：

   • 算法使用 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 的相应位置。

3. 返回结果：

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

1. 循环：代码的主体是一个 for 循环，它遍历 nums 数组一次，执行 N 次。
2. 队列操作：
   • 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)

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

综合分析：
算法所需的额外辅助空间主要由单调队列 win 决定，其大小与窗口大小 k 成正比。因此，空间复杂度为 O(k)。

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