滑动窗口算法-day2
目录
滑动窗口算法-day2
1.最多K个重复元素的最长子数组
题目
解析
1.解析：
- 思路比较简单，只要新进队的元素个数超了 k，就不断收缩左指针直到符合条件，最后更新最长子数组长度；
- 每个方案都包括了最右边的元素的最右边位置；
- 时间复杂度：L++最多运行n次，为O(n)；空间复杂度：使用哈希表，为O(n)；
代码
class Solution {
public:
int maxSubarrayLength(vector<int>& nums, int k) {
// 时间复杂度：O(n)
// 空间复杂度：O(n)
int n = nums.size();
int ans = 0;
int l = 0;
unordered_map<int,int> cnt;
for(int r = 0;r < n;r ++){
cnt[nums[r]] ++;
while(cnt[nums[r]] > k) {
cnt[nums[l]] --;
l ++;
}
ans = max(ans,r - l + 1);
}
return ans;
}
};2.找到最长的半重复子字符串
题目
解析
1.解析
- 核心思想：如果有两对相邻对，就让左指针右移，直到指向的元素等于前一个元素，相当于消去了第一个相邻对；
- 用 same 存储相邻对个数；每个方案都包括最右边的一对相邻对；
- 时间复杂度：O(n)；空间复杂度：O(1)；
代码
class Solution {
public:
int longestSemiRepetitiveSubstring(string s) {
// 时间复杂度：O(n)
// 空间复杂度：O(1)
int n = s.size();
int l = 0;
int ans = 1;
int same = 0;// 相邻对数量
for(int r = 1;r < n;r ++){
if(s[r] == s[r - 1]) same ++; // 相邻对加 1
// 如果有两对相邻对，就让左指针右移，直到指向的元素等于前一个
// 相当于消去了第一个相邻对
if(same == 2){
l ++;
while(s[l] != s[l - 1]) l ++;
same = 1; // 数量变为 1
}
ans = max(ans,r - l + 1);
}
return ans;
}
};3.最大连续1的个数 III
题目
解析
1.解析
- 这题唯一的区别就是只用记录 0 的个数，用一个变量 zero_num 代替了哈希表；
- 只要 0 的个数大于 k ，就移动左指针直到满足条件；
- 每个方案都包括最右边的 0；
- 时间复杂度：O(n)；空间复杂度：O(1)；
代码
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
// 时间复杂度：O(n)
// 空间复杂度：O(1)
int n = nums.size();
int ans = 0;
int zero_num = 0; // 记录0的个数，代替了哈希表
int l = 0;
for(int r = 0;r < n;r ++){
if(nums[r] == 0) zero_num ++;
while(zero_num > k){
if(nums[l] == 0){
zero_num --;
}
l ++;
}
ans = max(ans,r - l + 1);
}
return ans;
}
};4.统计最大元素出现至少K次的子数组
题目
解析
1.解析
- 核心思想：找到 L - R 出现 K 次的情况，这样就能保证只是出现 K 次(多余的可以出现在 L 指针左边，包含在后面的方案数中)；
- 本题同样只要记录 max 个数，用变量代替哈希表；
- 假设此时 L - R 间包含了 K 个 max，则移动左指针到左边那个 max 右边，下标为 L ，则此时满足条件的子数组个数即为 L；
- 每个合法方案都要包含最右边的 max；
- 举个例子：[1，3，2，3，5]，且 K = 2；L 指向 1，R 指向第二个 3，此时满足条件，L 移动到 2 ，答案数加上 L = 2；即为[1，3，2，3] 和 [3，2，3]；
- 时间复杂度：O(n)；空间复杂度：O(1)；
代码
class Solution {
public:
long long countSubarrays(vector<int>& nums, int k) {
// 时间复杂度：O(n)
// 空间复杂度；O(1)
int n = nums.size();
int max = 0;
for(int i = 0;i < n;i ++){
if(nums[i] > max) max = nums[i];
}
long long ans = 0;
int cnt = 0;
int l = 0;
for(int r = 0;r < n;r ++){
if(nums[r] == max) cnt ++;
while(cnt >= k){
if(nums[l] == max) cnt --;
l ++;
}
ans += l;
}
return ans;
}
};5.统计得分小于K的子数组个数
题目
解析
1.解析
- 核心思想：在包含右指针的基础条件下，去除不合格的左指针；
- 做法：枚举子数组右端点，去看对应的合法左端点的个数，然后根据题目的要求，求出合法左端点的最小值。
- 由于 L-R 此时为满足条件的最长子数组，答案加的一定要是包含右指针的方案数，计算为 R-L+1；
- 时间复杂度：O(n)；空间复杂度：O(1)；
代码
class Solution {
public:
long long countSubarrays(vector<int>& nums, long long k) {
// 时间复杂度：O(n)
// 空间复杂度：O(1)
int n = nums.size();
long long ans = 0;
int l = 0;
long long sum = 0;
for(int r = 0;r < n;r ++){
sum += nums[r];
while(sum * (r - l + 1) >= k){
sum -= nums[l];
l ++;
}
ans += r - l + 1;
}
return ans;
}
};6.将 x 减到 0 的最小操作数
题目
解析
1.解析
- 核心思想：反向思维，题目要求找两端最短的数组和等于 x，反向思考，题目变为找到中间最长的子数组，且其数组和等于 sum(nums[i]) - x = target；
- 题目变为滑动窗口问题，在包含右指针情况下，不断去除左指针的数，直到满足其余数的和小于等于 x；判断此时剩余值之和，若等于目标值，则更新最长数组长度；
- 最后答案即为数组长度减去该最长数组长度；
代码
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
// 时间复杂度：O(n)
// 空间复杂度：O(1)
int n = nums.size();
int ans = -1;
int sum = 0;
// t 为数组和，target 为减去 x 的剩余数组和，即为滑动窗口目标值
int t = 0;
for(int i = 0;i < n;i ++) t += nums[i];
int target = t - x;
// 目标值小于 0，一定无法实现
if(target < 0) return -1;
int l = 0;
for(int r = 0;r < n;r ++){
sum += nums[r];
while(sum > target) {
sum -= nums[l];
l ++;
}
if(sum == target) ans = max(ans,r - l + 1);
}
if(ans >= 0) return n - ans;
else return -1;
}
};7.总结
以下几点的滑动窗口算法的基本思路：
- 右指针：遍历整个数组；
- 左指针：根据题目条件不断右移，去除不符合的元素，使得 L-R 元素均满足题目条件；
- 答案方案数一定是建立在包含右指针的情况下去计算；
- 第六题的反向思维转换为滑动窗口非常巧妙，可以多思考几遍；