优化技巧--滑动窗口

目录

1.滑动窗口的作用

2.核心步骤📍

3.代码模板

4.手动演示推导过程📍

5.例题

---

1.滑动窗口的作用

维护数组中特定区间（窗口）内元素特性（如最大值、最小值、和）。

2.核心步骤📍

步骤 1：初始化数据结构

• 双端队列 deque<int> q：存储元素下标，确保队列中对应的元素值单调递减（维护最大值）或递增（维护最小值）。

• 结果数组 vector<int> res：存储每个窗口的极值。

步骤 2：遍历数组

对每个元素执行以下操作：

步骤 3：移除窗口外的过期元素

• 若队头元素下标小于当前窗口左边界 i - k + 1，说明该元素已超出窗口范围，弹出队头。

• 作用：确保队列中的元素均在当前窗口内。

步骤 4：维护队列单调性

• 维护最大值（降序队列）：若当前元素 nums[i] 大于等于队尾元素对应的值，则弹出队尾，直到队列为空或队尾元素值大于 nums[i]。

• 维护最小值（升序队列）：若当前元素 nums[i] 小于等于队尾元素对应的值，则弹出队尾，直到队列为空或队尾元素值小于 nums[i]。

• 作用：确保队列中的元素值单调递减 / 递增，队头即为当前窗口的极值。

步骤 5：当前元素入队

将当前元素下标 i 加入队尾。

步骤 6：窗口形成后记录结果

• 当遍历到第 k-1 个元素后，窗口大小达到 k，开始记录队头元素对应的值作为当前窗口的极值。

3.代码模板

#include <vector>
#include <deque>
using namespace std;// 滑动窗口最大值模板
vector<int> slidingWindowMax(const vector<int>& nums, int k) {deque<int> q; // 存储下标，队首始终是窗口的最大值下标vector<int> res;int n = nums.size();for (int i = 0; i < n; ++i) {// 移除窗口外的元素（左端点滑出）while (!q.empty() && q.front() <= i - k)q.pop_front();// 保持队列单调递减while (!q.empty() && nums[q.back()] <= nums[i])q.pop_back();// 当前元素入队q.push_back(i);// 记录当前窗口的最大值（队首为最大值）if (i >= k - 1) // 确保窗口已经形成res.push_back(nums[q.front()]);}return res;
}

4.手动演示推导过程📍

nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3

5.例题