本文共 995 字，大约阅读时间需要 3 分钟。
滑动窗口最大值问题优化思路
给定一个数组 nums，窗口大小为 k，从数组的最左侧滑动到最右侧，每次向右移动一位。任务是在每个窗口中找到最大值，并返回这些最大值的数组。
方法一：双端单调队列
思路概述
双端单调队列（Deque）是一种有效的数据结构，能够在两个端点进行插入和删除操作。对于滑动窗口最大值问题，双端单调队列可以用来维护窗口内可能的最大值候选。具体来说：
新增元素时，弹出队列尾部比当前元素小的所有元素，确保队列元素单调递减。 维护队列前部的位置，确保窗口长度不超过k。 当窗口位置满足条件时，记录当前窗口的最大值。 实现细节
队列维护：每次遍历数组中的新元素，处理队列确保其单调递减。 窗口滑动：动态调整左边界，确保窗口长度不超过k。 最大值记录：在窗口位置不再滑动时，记录队列前部元素的值作为最大值。
方法二：分块法
思路概述
分块法通过预处理前缀和后缀最大值，把问题分解为更小的子问题。具体方法如下：
前缀最大值数组：记录当前元素及其前k-1个元素的最大值。 后缀最大值数组：记录当前元素及其后k个元素的最大值。 窗口处理：对于长度为k的窗口，取左边界的前缀最大值和右边界的后缀最大值中的较大者。 实现细节
- 预处理：构建前缀和后缀最大值数组。
- 窗口处理：根据窗口位置，计算窗口的最大值。
- 组合结果：合并左右块内的最大值，得到最终结果。
方法选择与优化
选择原因：双端单调队列方法在时间和空间复杂度上都优于分块法，因为它避免了预处理步骤，并且处理单个元素的时间更高效。 空间优化：对于Python，使用deque模块实现更快，而数组模拟双端队列虽直观，但在处理大数组时效率较低。因此，优先选择deque模块实现。
新增元素处理流程
对于一个新元素nums[i]：
判断是否需要弹出队列尾部元素，确保新的元素比这些元素大，维护单调性。 将i入队，处理窗口长度超过k的情况，调整左边界。 当i >=k-1时，记录队列前部元素的值为窗口最大值。
验证与测试
通过示例测试，如示例1所示：输入 nums = [1,3,-1,-3,5,3,6,7]，k=3。预期输出 [3,3,5,5,6,7]。
验证过程：
预处理各个窗口，插入到队列中。 每次窗口满足条件时，记录最大值。 遍历完成后，得到预期结果。
结论
选择双端单调队列方法作为解决方案，既保证了算法的高效性，又易于理解和实现。
转载地址：http://ezaez.baihongyu.com/