1004. 最大连续1的个数 III
1.题目
给定一个二进制数组 nums
和一个整数 k
,如果可以翻转最多 k
个 0
,则返回 数组中连续 1
的最大个数 。
示例 1:
输入:nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出:6
解释:[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1,最长的子数组长度为 6。
示例 2:
输入:nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出:10
解释:[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1,最长的子数组长度为 10。
2.思路
找出最长子数组,0的个数不超过K个,
right
指针向右扩展窗口,寻找满足条件的子区间。- 当窗口不再满足条件时,通过移动
left
指针来缩小窗口,使其重新满足条件。
3.代码
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int left = 0, right = 0;
int len = 0;
while (right < nums.size()) {
// 当遇到0时,减少k,表示翻转了一个0
if (nums[right] == 0) {
--k;
}
++right;
// 当翻转的0超过k时,移动left指针收缩窗口
while (k < 0) {
if (nums[left] == 0) {
++k;
}
left++;
}
// 更新窗口内连续1的最大长度
len = max(len, right - left);
}
return len;
}
};
原文地址:https://blog.csdn.net/YQ20210216/article/details/142545176
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!