239. 滑动窗口最大值

Bin大约 5 分钟

239. 滑动窗口最大值

题目：滑动窗口最大值

描述：

给定一个整数数组 nums，和一个整数 k，表示滑动窗口的大小。滑动窗口从数组的最左侧向最右侧移动，每次移动一位。

要求：返回每次滑动窗口中的最大值。

示例：

示例 1:

输入: nums = [1,3,-1,-3,5,3,6,7], k = 3
输出: [3,3,5,5,6,7]
解释: 
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3   5] 3  6  7       5
 1  3  -1 [-3   5   3] 6  7       5
 1  3  -1  -3 [5   3   6] 7       6
 1  3  -1  -3   5 [3   6   7]      7

示例 2:

输入: nums = [1], k = 1
输出: [1]

示例 3:

输入: nums = [1,-1], k = 1
输出: [1,-1]

问题分析

题目目标

给定一个数组 nums 和窗口大小 k，要求在窗口每次移动时，找出窗口内的最大值。

滑动窗口性质

每次窗口包含 k 个连续的元素，窗口从数组左侧向右侧移动一位。
窗口的最大值会随着窗口的移动不断更新。

算法核心思想

为什么用双端队列？

双端队列（Deque）是一种支持在队列两端进行插入和删除的结构。我们用它来存储窗口中可能成为最大值的元素索引，同时通过以下两点确保它是正确的：

队列中始终保持递减顺序（从队首到队尾，对应 nums 的值递减）：
- 窗口内的最大值始终是队首索引对应的值。
- 如果一个新的数比队尾的数大，那么队尾的数不可能成为最大值，直接移除队尾。
队列只存储当前窗口的有效索引：
- 如果队首索引已经滑出窗口（i - k >= deque.peekFirst()），移除队首。

队列的意义

队列中的索引对应的值是当前窗口中可能成为最大值的候选。
队首的索引对应的值是当前窗口的最大值。

详细算法步骤

初始化：
- 使用一个双端队列 deque 存储数组索引。
- 使用结果数组 result 存储每次窗口的最大值。
遍历数组：
- 移除过期索引：如果队首索引已经不在当前窗口范围内（i - k >= deque.peekFirst()），移除队首。
- 维护单调递减性：从队尾开始移除所有比当前值小的索引，因为它们不可能成为当前窗口的最大值。
- 加入当前索引：将当前索引加入队尾。
- 记录最大值：当窗口形成（i >= k - 1），将队首的值加入结果。
返回结果。

详细代码实现

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        Solution solution = new Solution();
        int[] result = solution.maxSlidingWindow(nums, k);

        // 输出结果
        for (int i = 0; i < result.length; i++) {
            if (i > 0) System.out.print(" ");
            System.out.print(result[i]);
        }
        System.out.println();

        scanner.close();
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k == 0) return new int[0];

        // 初始化结果数组和双端队列
        int[] result = new int[nums.length - k + 1];
        Deque<Integer> deque = new LinkedList<>();

        // 遍历数组
        for (int i = 0; i < nums.length; i++) {
            // 1. 移除不在当前窗口范围内的索引
            if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }

            // 2. 移除队列中所有比当前元素小的索引
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            // 3. 将当前索引加入队列
            deque.offerLast(i);

            // 4. 如果窗口已经形成，记录窗口的最大值（队首）
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }

        return result;
    }
}

运行逻辑分析

输入：`nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3`

我们用双端队列 deque 存储索引，结果数组 result 存储最大值。

初始状态：
- deque = []，result = []
第一步：i = 0：
- 当前值：nums[0] = 1
- 队列为空，直接加入索引 0。
- deque = [0]
第二步：i = 1：
- 当前值：nums[1] = 3
- nums[1] > nums[deque.peekLast()]，移除索引 0。
- 加入索引 1。
- deque = [1]
第三步：i = 2：
- 当前值：nums[2] = -1
- 加入索引 2。
- deque = [1, 2]
- 窗口形成，记录最大值：result = [3]
第四步：i = 3：
- 当前值：nums[3] = -3
- 加入索引 3。
- deque = [1, 2, 3]
- 窗口形成，记录最大值：result = [3, 3]
第五步：i = 4：
- 当前值：nums[4] = 5
- 索引 1 已过期，移除。
- 移除比 5 小的索引 2, 3。
- 加入索引 4。
- deque = [4]
- 窗口形成，记录最大值：result = [3, 3, 5]
继续滑动窗口：
- 每次移除过期索引、维护队列单调递减、记录结果。

关键问题：为什么这样可以保证正确性？

1. 保持单调性

每次新加入元素时，移除比它小的所有元素，确保队列从大到小排列。
这样队首始终是窗口内的最大值。

2. 移除过期索引

如果队首索引已经滑出窗口范围，移除队首，保证队列只包含当前窗口的值。

3. 窗口形成后，队首即最大值

因为队列是单调递减的，队首始终是当前窗口的最大值。

时间复杂度分析

每个元素最多被插入和删除一次，时间复杂度为 O(n)。
队列操作的开销为常数，遍历整个数组需要线性时间。

总时间复杂度：O(n)。

总结

为什么队列能保证正确性？
- 队列单调递减，保证最大值始终在队首。
- 每次只移除无用元素（过期或比当前值小）。
空间复杂度：O(k)（队列最多存储窗口大小的索引）。