leetcode1004. Max Consecutive Ones III

1004. Max Consecutive Ones III

Medium

1806FavoriteShare

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. 1 <= A.length <= 20000
2. 0 <= K <= A.length
3. A[i] is 0 or 1 

Accepted

8,975

Submissions

17,048

Seen this question in a real interview before?

 

Yes

 

No

01串，最多只有k次可以改变0为1，问最长的01串

双指针维护1的区间，然后移动取max，具体看代码

class Solution {
public:
    int longestOnes(vector<int>& A, int K) {
        int l = 0,r = 0,cnt = 0,ans = 0;
        while(l <= r && r < A.size()){
            if(A[r] == 1){ 
               r++;
            }else{
               if(cnt == K){
                 while(l <= r){
                    if(A[l] == 1) l++;
                    else{
                        l++; 
                        r++;
                        break;
                    }
                 }
               }else{
                 cnt++;r++;
               }
            }
            ans = max(ans,r - l);
        }
        return ans;
    }
};