LeetCode上最大连续1的个数 III,中等难度,是之前2021/02/15 每日一题 最大连续1的个数 (2种方法)的升级版,也是用滑动窗口来解题,记录下解题思路
传入数组A和最多可改变数组K,求A中的子数组在改变K个元素之后,最大连续1数组的长度
这里通过一个滑动窗口来遍历整个A数组,不关注窗口内的元素是什么顺序,只要里面的0的数量等于K窗口就不能增加了:
- 每次扩展的时候,记录下添加进入窗口的元素,如果为1不操作,如果为0记下数量用
count
来保存 - 当
count > K
的情况,证明窗口内0的元素大于传入的K,那么就要循环移动left
,并且判断每个left
对应的元素是否为0,如果为0那么移出之后count
就要减1 - 之后重复循环,遍历完数组全部元素即可
是个很标准的滑动窗口的题,直接上代码
var longestOnes = function(A, K) {
// 定义滑动窗口的左右
let left = 0,right = 0
// 用于保存A的长度
let len = A.length
// 用于记录当前窗口内有多少个0
let count = 0
// 记录当前窗口长度
let window = 0
// 返回结果
let res = 0
// 开始遍历整个数组A
for(let i = 0;i<len;i++) {
// 判断当前right所指位置是否为0
if(A[right] === 0) {
count++
}
// 当count > K的情况,就是当前窗口内的0的数量多于传入的K
while(count > K) {
// 1.移出left对应的元素,如果left对应的是0,那么count也要减1
if(A[left] === 0) count = count - 1
// 2.left向右移动
left = left + 1
}
// 记录下当前window长度,+1是因为left = right的情况窗口长度也算为1
window = right - left + 1
// 需要比较当前窗口和之前保存的结果,取最大值
res = Math.max(res,window)
// 窗口扩展
right++
}
return res
};