1004. number of maximum consecutive 1 III ●●

1004. Maximum continuous 1 The number of III ●●

describe

Given a binary array nums And an integer k, If you can flip up to k individual 0 , Then return to Continuous in array 1 Maximum number of .

Example

Input ：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
Output ：6
explain ：[1,1,1,0,0,1,1,1,1,1,1]
Bold numbers from 0 Flip to 1, The longest subarray length is 6.

Answer key

1. The sliding window （ Double pointer ）

hold 「 At most K individual 0 become 1, Only include 1 Length of the longest subarray of 」
Convert to
「 Find the longest subarray , A maximum of... Is allowed in this subarray K individual 0 」.

This problem is to find the maximum continuous subinterval , You can use the sliding window method . The limiting condition of sliding window is ： There are at most... In the window K individual 0.

Code thinking ：

1. Use left and right Two pointers , Point to the left and right boundaries of the sliding window .
2. right Active right shift ：right The pointer moves one step at a time . When A[right] by 0, Description: a... Is added in the sliding window 0;
3. left Passive right shift ： Judge the current window 0 The number of , If you exceed K, be left The pointer is forced to move to the right , Until... In the window 0 The number of is less than or equal to K until .
4. The maximum length of the sliding window is the desired .

With A= [1,1,1,0,0,0,1,1,1,1,0], K = 2 For example , The following diagram shows the movement of the two pointers of the sliding window .

• Time complexity ：O(N), Because each element is traversed only once .
• Spatial complexity ：O(1), Because I use a constant space .

class Solution {
    
public:
    int longestOnes(vector<int>& nums, int k) {
    
        int n = nums.size();
        int l = 0, ans = 0, zero = 0;
        for(int r = 0; r < n; ++r){
    
            if(nums[r] == 0) ++zero;		//  Zero number  + 1
            while(zero > k){
    				//  The number of zeros is greater than k when 
                if(nums[l] == 0) --zero;	//  Move the left pointer 
                ++l;
            }
            ans = max(ans, r - l + 1);		//  Calculate the length of the current window 
        }
        return ans;
    }
};

2. The prefix and + Two points search

Enumeration interval Left end point / Right endpoint , Then find its satisfaction 「 appear 0 No more than k Time 」 The farthest right endpoint of / Farthest left endpoint .

For quick judgment [ l, r ] In between 0 The number of , We need to use The prefix and .

hypothesis [l, r ] The interval length of is len, Interval sum is tol, Then there comes 0 The number of len - tol, And again k Compare .

Because there will be no negative weight in the array , Therefore, prefixes and arrays have 「 monotonicity 」, Then it must be satisfied 「 One paragraph satisfies len - tol <= k, Another paragraph is not satisfied len - tol <= k」.

therefore , For a affirmatory 「 Left end point / Right endpoint 」 for , With 「 Its farthest right endpoint / Farthest left endpoint 」 Prefix and number axis of the dividing point , have 「 Dichotomy 」. You can find the split point by dichotomy .

The following code has a defined right endpoint , To find the first left boundary that satisfies the condition from left to right .

• Time complexity ：$O(n\log n)$
• Spatial complexity ：$O(n)$

class Solution {
    
public:
    bool check(vector<int>&sum, int l, int r, int k){
       //  Judge  l ~ r  Within the interval  0  Whether the number of is  k  Within the scope of 
        int len = r - l + 1;
        return len - (sum[r+1] - sum[l]) <= k;
    }

    int longestOnes(vector<int>& nums, int k) {
    
        int n = nums.size(), ans = 0;
        if(n == 0) return 0;
        vector<int> sum(n+1, nums[0]);
        for(int i = 1; i <= n; ++i) sum[i] = sum[i-1] + nums[i-1];  //  Statistical prefix and , Subscript  i  The prefix and within are  sum[i+1]
        for(int i = 0; i < n; ++i){
                 //  With  i  For the right border 
            int l = 0, r = i;
            while(l < r){
                           //  Binary search satisfies   With  i  For the right border ,0  The number of is less than or equal to  k  Of   First left boundary from left to right 
                int mid = (l+r)>>1;
                if(check(sum, mid, i, k)){
    
                    r = mid;                    //  The boundary pushes to the left 
                }else{
    
                    l = mid + 1;                //  dissatisfaction , Push right 
                }
            }
            if(check(sum, r, i, k)) ans = max(ans, i - r + 1);  //  Check again , Calculate the interval length 
        }
        return ans;
    }
};

About again after two points check Explanation ： because 「 Two points 」 The essence is to find the dividing point satisfying a certain property , Usually one of our properties will be 「 Non equivalent conditions 」, Not necessarily =.

For example, we are familiar with ： Find the target value from a non decreasing group , Find the return subscript , Otherwise return to -1.

When the target value does not exist ,「 Two points 」 The number found should be the closest number in the array that is smaller or larger than the target value . Therefore, after the end of the two points, we will start with check Reuse is a good habit .