1. 题目描述
给定一个由若干 0
和 1
组成的数组 A
,我们最多可以将 K
个值从 0 变成 1 。
返回仅包含 1 的最长(连续)子数组的长度。
示例 1:
输入:A = [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:
输入:A = [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。
提示:
初始化两个指针left和right,开始两个指针都指向第一个数字。每次遍历数组的时候,右指针一直向右移动,然后使用count来同步统计窗口的长度。
如果窗口内的0的个数大于K,那么就向右移动左指针,直到窗口中的0的个数不大于K。在每次遍历完之后保留最大的窗口值,这样最后就能得到最多连续的1。
复杂度分析:
- 时间复杂度:O(n),其中 n 是数组 A 的长度。我们至多需要遍历该数组两次(左右指针各一次)。
- 空间复杂度:O(1),我们只需要常数的空间保存res、left、right、count。
3. 代码实现
/**
* @param {number[]} A
* @param {number} K
* @return {number}
*/
var longestOnes = function(A, K) {
let left = 0, count = 0, res = 0
for(let right = 0; right < A.length; right++){
if(A[right] === 0){
count++
}
while(count > K){
if(A[left++] === 0){
count--
}
}
res = Math.max(res, right - left + 1)
}
return res
};
4. 提交结果