最大连续1 的个数Ⅲ(滑动窗口)
题目:
给定一个二进制数组 nums
和一个整数 k
,如果可以翻转最多 k
个 0
,则返回 数组中连续 1
的最大个数 。
首先,我们需要了解题干的意思:我们需要将给定的一个只有 0 和 1 的数组,最多将其中 k 个0改变为 1 ,来得到一个连续1最长的子串。
假设输入:nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2; 我们最多可以将第 6 个和第 11 个 0 改为 1,得到[1,1,1,0,0,1,1,1,1,1,1],其中最大连续1 的个数为 6.
基本思路:
我们肯定不能真的将原数组中的成员不断修改,因为这样会将题目变得更加复杂,那么我们可以使用一个变量 num_zero 做零计数器。
题目提供k次机会把0改变为1,开始时两个指针 left 和 right 都为 0,即最开始的那个数;
右指针 right 遍历数组,遇到0就让 num_zero++。当num_zero 大于 k 的时候,就要移动left 前进。
实现原理如下:
- 初始化两个指针
left
和right
,分别指向数组的第一个元素和第二个元素。 - 初始化一个计数器
num_zero
,用于记录数组中0的个数。 - 初始化一个变量
max
,用于记录连续1的最大长度。 - 使用一个
while
循环,当left
小于数组长度减去max
时,执行以下操作: a. 使用另一个while
循环,当num_zero
小于等于k
时,执行以下操作: i. 如果nums[right]
等于0,将num_zero
加1。 ii. 如果num_zero
大于k
,计算right
与left
之间的距离,如果大于max
,则将max
更新为right
与left
之间的距离。 iii. 如果num_zero
大于k
,跳出内层循环。 b. 将left
加1,如果nums[left - 1]
等于0,将num_zero
减2。 - 在循环结束后,返回
max
。
right和left之间的最长区间就是 连续1的最大个数
class Solution {
public:
int longestOnes(vector& nums, int k) {
int left = 0, right = 0;
int num_zero = 0;
int max = 0;
while (left < nums.size() - max) {//{ 1,1,1,0,0,0,1,1,1,1,0 };
while (num_zero k) {
if (right - left > max)
max = right - left;
break;
}
right++;
if (right >= nums.size()) {
max = right - left;
return max;
}
}
left++;
if (nums[left - 1] == 0) {
num_zero-= 2;
}
}
return max;
}
};
int main() {
Solution s1;
vector v1{ 1,1,1,0,0,0,1,1,1,1,0 };
vector v2{ 0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1 };
cout << s1.longestOnes(v2, 3) << endl;
return 0;
}