Max Consecutive Ones III
程序员文章站
2024-03-06 20:15:56
...
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
思路:典型的同向双指针题目,count最长的区间使得最多含有K个0;O(N);
class Solution {
public int longestOnes(int[] A, int K) {
if(A == null || A.length == 0 || K < 0) {
return 0;
}
int maxlen = 0;
int count = 0;
int j = 0;
// two pointers algorithm;
for(int i = 0; i < A.length; i++) {
// move j;
while(j < A.length && count <= K) {
if(A[j] == 0) {
if(count == K) {
break;
}
count++;
}
j++;
}
// update result;
maxlen = Math.max(maxlen, j - i);
// move i;
if(A[i] == 0) {
count--;
}
}
return maxlen;
}
}
下一篇: 浅析java 10中的var关键字用法
推荐阅读
-
Max Consecutive Ones III
-
【leetcode】1004. 最大连续1的个数 III(max-consecutive-ones-iii)(滑动窗口)[中等]
-
Max Consecutive Ones III
-
LeetCode--1004. Max Consecutive Ones III
-
leetcode 1004 Max Consecutive Ones III
-
LeetCode 1004 max-consecutive-ones-iii
-
【LeetCode】1004. Max Consecutive Ones III 最大连续1的个数 III(Medium)(JAVA)
-
LeetCode——1004. 最大连续1的个数 III(Max Consecutive Ones III)[中等]——分析及代码(Java)
-
leetcode1004. Max Consecutive Ones III
-
leetcode 1004.最大连续1的个数 Max Consecutive Ones III Java版本