Max Consecutive Ones III
程序员文章站
2024-03-06 09:57:55
...
Given an array A
of 0s and 1s, we may change up to K
values from 0 to 1.
Return the length of the longest (contiguous) subarray that contains only 1s.
Example 1:
Input: A = [1,1,1,0,0,0,1,1,1,1,0], K = 2 Output: 6 Explanation: [1,1,1,0,0,1,1,1,1,1,1] Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
Example 2:
Input: A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3 Output: 10 Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1] Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
Note:
1 <= A.length <= 20000
0 <= K <= A.length
-
A[i]
is0
or1
题目理解:
给定一个由0和1组成的数组,将其中的某K个0变成1之后,数组中存在的最长的连续的1有多长
解题思路:
用dp[i]表示到i位置为止,有多少个0,使用两个指针left和right,每次固定left,移动right,保证right - left <= K,记录最大的(right - left)。然后将left加1,继续移动right。right可以一直增加,因为如果right变小,那么(right - left)一定小于已经记录的最大值。
class Solution {
public int longestOnes(int[] A, int K) {
int len = A.length;
int[] record = new int[len + 1];
for(int i = 1; i < len + 1; i++){
record[i] = record[i - 1];
if(A[i - 1] == 0)
record[i]++;
}
int left = 0, right = 0, res = 0;
while(true){
while(right < len && record[right + 1] - record[left] <= K)
right++;
res = Math.max(res, right - left);
if(right == len)
break;
left++;
}
return res;
}
}
推荐阅读
-
Max Consecutive Ones III
-
LeetCode--1004. Max Consecutive Ones III
-
leetcode 1004 Max Consecutive Ones III
-
LeetCode——1004. 最大连续1的个数 III(Max Consecutive Ones III)[中等]——分析及代码(Java)
-
leetcode1004. Max Consecutive Ones III
-
leetcode 1004.最大连续1的个数 Max Consecutive Ones III Java版本
-
LeetCode1004.Max Consecutive Ones III(最大连续1的个数 III)