1004.Max-Consecutive-Ones-III

1004. Max Consecutive Ones III

题目地址

题目描述

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] is 0 or 1

代码

Approach #1 Sliding Window

class Solution {
public int longestOnes(int[] A, int K) {
int l = 0;
int zeros = 0;
int ans = 0;
for (int r = 0; r < A.length; r++) {
if (A[r] == 0) {
zeros++;
}
while (zeros > K) {
if (A[l++] == 0) {
zeros--;
}
}
ans = Math.max(ans, r - l + 1);
}
return ans;
}
}

#2

class Solution {
public int longestOnes(int[] A, int K) {
int left = 0;
int right;
for (right = 0; right < A.length; right++) {
if (A[right] == 0) {
K--;
}
if (K < 0) {
if (A[left] == 0) {
K++;
}
left++;
}
}
return right - left;
}
}