IT评测·应用市场-qidao123.com

标题: C++ 滑动窗口 [打印本页]

作者: 十念 时间: 2025-3-10 20:46
标题: C++ 滑动窗口
前言

C++ 中滑动窗口分两种，一种是给定窗口长度，另有一种是不定长窗口长度。
本篇文章主要解说这两种状态的滑动窗口，结合例题让读者更好的明白
一、给定窗口长度K

一般的，对于给定窗口长度的题，通常要求我们对窗口内的元素举行一些操作，办理一些问题，具体问题具体分析。
给定窗口长度的标题通常要求办理以下问题：

找到每个窗口内的最大值或最小值。
计算每个窗口的和或均匀值。
统计满足条件的子数组数量。
找到满足条件的最长或最短子数组。
统计窗口内的唯一元素数量。

  可以在 O(n) 的时间复杂度内办理问题
标题1：

力扣 1343 题大小为 K 且均匀值大于等于阈值的子数组数量
给你一个整数数组 arr 和两个整数 k 和 threshold 。
请你返回长度为 k 且均匀值大于等于 threshold 的子数组数量。
示例 1：
输入：arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
输出：3
解释：子数组 [2,5,5],[5,5,5] 和 [5,5,8] 的均匀值分别为 4，5 和 6 。其他长度为 3 的子数组的均匀值都小于 4 （threshold 的值)。
  示例 2：
输入：arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
输出：6
解释：前 6 个长度为 3 的子数组均匀值都大于 5 。注意均匀值不是整数
  直接上代码：

class Solution {
public:
int numOfSubarrays(vector<int>& arr, int k, int threshold) {
int ans = 0;
int s = 0; // 维护窗口元素和
for (int i = 0; i < arr.size(); i++) {
// 1. 进入窗口
s += arr[i];
if (i < k - 1) { // 窗口大小不足 k
continue;
}
// 2. 更新答案
ans += s >= k * threshold;
// 3. 离开窗口
s -= arr[i - k + 1];
}
return ans;
}
};

复制代码

解释：总共主要分3步，不敷窗口长度的先进入窗口，满足长度等于窗口大小后更新答案，之后就是窗口往后移，右边元素进入窗口，左边元素移除窗口，然后不断更新答案。
标题2：

力扣2461题长度为 K 子数组中的最大和
给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：

子数组的长度是 k，且
子数组中的全部元素 各不雷同。

返回满足题面要求的最大子数组和。假如不存在子数组满足这些条件，返回 0 。
子数组 是数组中一段连续非空的元素序列。
示例 1：

输入：nums = [1,5,4,2,9,9,9], k = 3
输出：15
解释：nums 中长度为 3 的子数组是：
- [1,5,4] 满足全部条件，和为 10 。
- [5,4,2] 满足全部条件，和为 11 。
- [4,2,9] 满足全部条件，和为 15 。
- [2,9,9] 不满足全部条件，因为元素 9 出现重复。
- [9,9,9] 不满足全部条件，因为元素 9 出现重复。
因为 15 是满足全部条件的所有子数组中的最大子数组和，所以返回 15 。

复制代码

示例 2：

输入：nums = [4,4,4], k = 3
输出：0
解释：nums 中长度为 3 的子数组是：
- [4,4,4] 不满足全部条件，因为元素 4 出现重复。
因为不存在满足全部条件的子数组，所以返回 0 。

复制代码

上代码看解释来明白

class Solution {
public:
long long maximumSubarraySum(vector<int>& nums, int k) {
int n = nums.size(); // 获取数组的长度
long long sum = 0; // 当前窗口的和
long long ma = 0; // 用于存储最大子数组和
unordered_map<int, int> hash; // 哈希表，用于记录窗口内每个元素的出现次数
// 初始化窗口的前 k-1 个元素
for (int i = 0; i < k - 1; i++) {
hash[nums[i]]++; // 更新元素的出现次数
sum += nums[i]; // 将元素加入当前窗口的和
}
// 遍历数组，维护一个大小为 k 的滑动窗口
for (int i = k - 1; i < n; i++) {
hash[nums[i]]++; // 将当前元素加入窗口，并更新其出现次数
sum += nums[i]; // 更新当前窗口的和
// 如果窗口内有 k 个不同的元素，更新最大和
if (hash.size() == k) {
ma = max(ma, sum); // 更新最大子数组和
}
// 移动窗口：移除窗口左侧的元素
hash[nums[i - k + 1]]--; // 减少左侧元素的出现次数
if (hash[nums[i - k + 1]] == 0) {
hash.erase(nums[i - k + 1]); // 如果元素的出现次数为 0，从哈希表中移除
}
sum -= nums[i - k + 1]; // 从当前窗口的和中移除左侧元素
}
return ma; // 返回最大子数组和
}
};

复制代码

逻辑解释：

初始化窗口：
- 使用一个哈希表 hash 来记录窗口内每个元素的出现次数。
- 使用 sum 来记录当前窗口的和。
- 起首将前 k-1 个元素加入窗口，初始化 sum 和 hash。
滑动窗口遍历：
- 从第 k-1 个元素开始遍历数组。
- 每次将当前元素 nums 加入窗口，并更新其出现次数和窗口的和。
- 检查窗口内是否有 k 个不同的元素：
  
  假如有 k 个不同的元素，更新最大和 ma。
- 移动窗口：移除窗口左侧的元素 nums[i-k+1]，更新其出现次数和窗口的和。
  
  假如某个元素的出现次数变为 0，从哈希表中移除该元素。
返回结果：

遍历结束后，ma 中存储的就是满足条件的最大子数组和。

二、不定长窗口大小

不定长滑动窗口主要分为三类：求最宗子数组，求最短子数组，以及求子数组个数。
通常我们对于处理串的问题时，使用暴力算法超时的时候，就可以思量使用滑动窗口来优化时间了
看标题来加深明白
标题1：

力扣904题水果成篮
你正在拜望一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits 是第 i 棵树上的水果种类。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

你只有两个篮子，而且每个篮子只能装 单一范例 的水果。每个篮子能够装的水果总量没有限定。

你可以选择任意一棵树开始采摘，你必须从每棵树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果范例。每采摘一次，你将会向右移动到下一棵树，并继续采摘。

一旦你走到某棵树前，但水果不符合篮子的水果范例，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的最大数量。
示例 1：

输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。
复制代码
示例 2：

输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。
复制代码
示例 3：

输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。
复制代码
示例 4：

输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。
复制代码
AC代码

class Solution {
public:
int totalFruit(vector<int>& fruits) {
 int n = fruits.size(); // 获取果树的数量
 unordered_map<int, int> hash; // 哈希表，用于记录当前窗口内每种水果的数量
 int left = 0; // 滑动窗口的左边界
 int ma = 0; // 用于记录最多可以采摘的水果数量
 // 遍历所有果树，right 表示滑动窗口的右边界
 for (int right = 0; right < n; right++) {
 hash[fruits[right]]++; // 将当前果树的水果加入窗口，并更新其数量
 // 如果窗口内有超过两种水果，需要收缩窗口
 while (hash.size() > 2) {
 int out = fruits[left]; // 获取窗口左侧的水果
 hash[out]--; // 减少左侧水果的数量
 if (hash[out] == 0) {
 hash.erase(out); // 如果某种水果的数量变为 0，从哈希表中移除
 }
 left++; // 移动左边界，缩小窗口
 }
 // 更新最多可以采摘的水果数量
 // 当前窗口的水果数量为 right - left + 1
 ma = max(ma, right - left + 1);
 }
 return ma; // 返回最多可以采摘的水果数量
}
};
复制代码
很多题套路都差不多的，对于不定长滑动窗口大小，用的比较多的就是哈希表来存储

初始化：

n：果树的总数。

hash：哈希表，用于记录当前窗口内每种水果的数量。

left：滑动窗口的左边界，初始值为0。

ma：用于记录最多可以采摘的水果数量，初始值为0。

滑动窗口遍历：

使用 right 作为滑动窗口的右边界，从左到右遍历全部果树。

每次将当前果树的水果加入窗口，并更新其在哈希表中的数量。

收缩窗口：

假如当前窗口内有凌驾两种水果（hash.size() > 2），需要收缩窗口。

移动左边界 left，移除窗口左侧的水果，直到窗口内只剩下两种水果。

更新结果：

每次调解窗口后，计算当前窗口的水果数量（right - left + 1），并更新最大值 ma。

返回结果：

遍历结束后，ma 中存储的就是最多可以采摘的水果数量。

 标题2：

力扣1695题删除子数组的最大得分
给你一个正整数数组 nums ，请你从中删除一个含有 多少不同元素 的子数组。删除子数组的得分就是子数组各元素之和。
返回 只删除一个 子数组可得到的 最大得分 。
假如数组 b 是数组 a 的一个连续子序列，即假如它等于 a[l],a[l+1],...,a[r] ，那么它就是 a 的一个子数组。
示例 1：

输入：nums = [4,2,4,5,6]
输出：17
解释：最优子数组是 [2,4,5,6]
复制代码
示例 2：

输入：nums = [5,2,1,2,5,2,1,2,5]
输出：8
解释：最优子数组是 [5,2,1] 或 [1,2,5]
复制代码
这题和上题非常相识，都是同一个套路，变的就是标题给的条件

class Solution {
public:
int maximumUniqueSubarray(vector<int>& nums) {
 int n = nums.size(); // 获取数组的长度
 long long ma = 0; // 用于存储最大唯一子数组的和
 int left = 0; // 滑动窗口的左边界
 long long sum = 0; // 当前窗口内所有元素的和
 unordered_map<int, int> hash; // 哈希表，用于记录窗口内每个元素的出现次数
 // 遍历数组，right 表示滑动窗口的右边界
 for (int right = 0; right < n; right++) {
 // 将当前元素加入窗口，并更新其出现次数
 hash[nums[right]]++;
 sum += nums[right]; // 更新当前窗口的和
 // 如果当前元素的出现次数大于 1，说明窗口内有重复元素
 // 需要收缩窗口，移除窗口左侧的元素，直到窗口内没有重复元素
 while (hash[nums[right]] > 1) {
 sum -= nums[left]; // 从窗口的和中移除左侧元素
 hash[nums[left]]--; // 更新左侧元素的出现次数
 left++; // 移动左边界
 }
 // 更新最大唯一子数组的和
 ma = max(ma, sum);
 }
 return ma; // 返回最大唯一子数组的和
}
};
复制代码
万变不离其宗，只有多刷题才能加深算法的印象。祝各位读者在刷算法的路上越走越远 0v0!

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/) Powered by Discuz! X3.4