问题描述
给定一个由若干
0
和1
组成的数组A
,我们最多可以将K
个值从 0 变成 1 。返回仅包含 1 的最长(连续)子数组的长度。
示例1
给定一个由若干 0 和 1 组成的数组 A,我们最多可以将 K 个值从 0 变成 1 。
返回仅包含 1 的最长(连续)子数组的长度。
示例2
给定一个由若干 0 和 1 组成的数组 A,我们最多可以将 K 个值从 0 变成 1 。
返回仅包含 1 的最长(连续)子数组的长度。
解题过程
该题解答为滑动窗口解决方案,运行时间3ms,打败95%玩家,后续给出一个网友提供的解决方案,运行时间1ms,打败100%玩家的答案
- 定义左右边界left right,循环直到right达到末端;
- 定义zeroCount用于记录当前窗口内出现了的0次数,并且判断如果记录总数大于K,则此次窗口达到最大,记录当前窗口宽度,根据当前左侧即将滑出元素是否为0更新0记录字段,并且左侧left右移;
- 最后循环完之后需要再判断一次最终达到右侧的窗口宽度是否是最大的宽度;
答案
class Solution {
public int longestOnes(int[] A, int K) {
//记录窗口最大宽度
int max = 0;
//窗口左边界
int left = 0;
//窗口右边界
int right = 0;
//窗口内0数量
int zeroCount = 0;
while (right < A.length) {
//记录是否出现0
zeroCount += A[right]^1;
if (zeroCount > K ) {
//如果记录的0大于K,则需要将左侧一个元素移出窗口,并且如果左侧即将移除的元素为0,则需要更新zeroCount字段
zeroCount -= A[left]^1;
max = Math.max(max, right - left);
left++;
}
++right;
}
max = Math.max(max, right - left);
return max;
}
}
网友优秀答案
class Solution {
public int longestOnes(int[] A, int K) {
int l = 0, r = 0;
while (r < A.length) {
if (A[r++] == 0) K--;
if (K < 0 && A[l++] == 0) K++;
}
return r - l;
}
}