LeetCode第239题：滑动窗口k内求最大值

来源：LeetCode第239题
难度：困难

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k
个数字。滑动窗口每次只向右移动一位。
这段代码实现了 滑动窗口最大值 的问题，使用了 双端队列（deque）来高效地找到数组 nums 中每个大小为 k 的滑动窗口的最大值。以下是代码的详细解析：

代码概述

public int[] maxSlidingWindow(int[] nums, int k) {
    int index = 0, len = nums.length;
    int[] ans = new int[len - k + 1];
    // 双端队列，存储元素的下标
    Deque<Integer> deque = new ArrayDeque<>();
    
    for (int i = 0; i < len; i++) {
        // 如果队列中队头元素和当前元素位置相差i-k，相当于队头元素要出窗口了，就把队头元素给移除。
        if (!deque.isEmpty() && deque.peekFirst() <= i - k)
            deque.pollFirst();
        
        // 在添加一个值之前，前面比他小的都要被移除掉，并且还要保证窗口中队列头部元素永远是队列中最大的。
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i])
            deque.pollLast();
        
        deque.addLast(i); // 当前元素的下标加入到队列的尾部。
        
        // 当窗口的长度大于等于k个的时候才开始计算（注意这里的i是从0开始的）。
        if (i >= k - 1)
            // 队头元素是队列中最大的，把队列头部的元素加入到数组中。
            ans[index++] = nums[deque.peekFirst()];
    }
    
    return ans;
}

详细解析

初始化：

int index = 0: 用于跟踪结果数组 ans 中下一个最大值要存储的位置。
int len = nums.length: nums 数组的长度。
int[] ans = new int[len - k + 1]: 结果数组，用于存储每个滑动窗口的最大值。大小为 len - k + 1，因为数组中有这么多大小为 k 的窗口。
Deque deque = new ArrayDeque<>(): 创建一个双端队列，用于存储数组元素的下标。
遍历数组：

for (int i = 0; i < len; i++): 遍历每一个元素。
移除超出窗口的下标：

if (!deque.isEmpty() && deque.peekFirst() <= i - k): 检查队列的队头（最大值的下标）是否超出了当前窗口的范围。如果超出，移除队头元素。
维护队列中的最大值：

while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]): 当当前元素 nums[i] 大于队列中对应的元素时，移除队列末尾的下标。这确保队列中的下标对应的元素是当前窗口中的潜在最大值。
deque.addLast(i): 将当前元素的下标 i 加入到队列的末尾。
记录最大值：

if (i >= k - 1): 判断当前索引 i 是否到达第一个有效窗口的结束（即 i 至少为 k - 1）。
ans[index++] = nums[deque.peekFirst()]: 将队列头部的元素（即当前窗口的最大值）存储到结果数组 ans 中。
返回结果：

return ans;: 返回包含每个滑动窗口最大值的数组。
时间复杂度
该算法的时间复杂度为 O(n)，其中 n 是 nums 数组的元素数量。每个元素最多被加入和移除队列一次，使得算法在处理大输入时非常高效。
空间复杂度
空间复杂度为 O(k)，因为在最坏情况下，队列最多可以存储 k 个下标。
示例
假设 nums = [1, 3, -1, -3, 5, 3, 6, 7] 且 k = 3：

滑动窗口的最大值如下：
窗口 1: [1, 3, -1] -> 最大值 = 3
窗口 2: [3, -1, -3] -> 最大值 = 3
窗口 3: [-1, -3, 5] -> 最大值 = 5
窗口 4: [-3, 5, 3] -> 最大值 = 5
窗口 5: [5, 3, 6] -> 最大值 = 6
窗口 6: [3, 6, 7] -> 最大值 = 7
最终的输出将是 [3, 3, 5, 5, 6, 7]。

这种方法既高效又清晰，利用双端队列有效地维护滑动窗口中的最大值。