题解

1. 自己的做法很麻烦并且时间复杂度高，最坏 O ( n 2 ) O(n^2) O(n2)
2. 原因是没有想到去数学推导，一步一步去想很费劲，，，应该改掉这个毛病。
3. 想到了二分的做法，但是写麻烦了，首先统计了所有0块所在的初始位置和个数，记为数组a，然后遍历所有的地方去填充0，这个时候就不能方便的从a中得到填充到哪为止，从而陷入了困境。
4. 科学的做法，参造官方：
   • 首先要想得到最大的连续的1的个数，所有的K个的份额一定是把多个1的块连成一个块这一点没有疑问。
   • 那么问题转化为想清这一步下面就简单了，我们隐隐约约感觉到，一个K，一个目的求最大的1的长度，和前缀和有关
   • 我们假设 P [ i ] P[i] P[i]代表 [ 0 , i ] [0,i] [0,i]中 1 1 1的个数的前缀和。
   • 那么 P [ r i g h t ] − P [ l e f t − 1 ] P[right]-P[left-1] P[right]−P[left−1]代表区间 [ l e f t , r i g h t ] [left,right] [left,right]中的 1 1 1的个数的，我们就是要找到满足 P [ l e f t ] − P [ l e f t − 1 ] < = k P[left]-P[left-1]<=k P[left]−P[left−1]<=k的最大的 r i g h t − l e f t + 1 right-left+1 right−left+1的长度，
   • 怎么找到这个left?二分查找，时间复杂度 O ( n l o g ( n ) ) O(nlog(n)) O(nlog(n))
     • 这个时候我么遍历 r i g h t right right，为什么遍历 r i g h t right right？因为下面的c++中有 l o w e r _ b o u n d ( ) lower\_bound() lower_bound()这个函数可以方便的使用，找到满足条件的最小的 l e f t left left就好了。
     • 也就是 P [ l e f t − 1 ] > = P [ r i g h t ] − k P[left-1]>=P[right]-k P[left−1]>=P[right]−k，我们可以使用 l o w e r _ b o u n d ( ) lower\_bound() lower_bound()函数方便的找到最小的left
     • 为了不处理边界条件，我们将 P [ ] P[] P[]数组整个向右移动 1 1 1，这样 P [ i ] P[i] P[i]就代表 [ 0 , i − 1 ] [0,i-1] [0,i−1]中 1 1 1的个数。
     • 于是我们有了下面的代码
   • 滑动窗口，时间复杂度 O ( n ) O(n) O(n)
     • 代码很短，如代码所示

二分代码

class Solution {
public:
    int longestOnes(vector<int>& A, int K) {
        int n=A.size();
        vector<int>P(n+2);
        for(int i=1;i<=n;i++){
            P[i]=P[i-1]+(1-A[i-1]);
        }
        int res=-1;
        for(int i=n-1;i>=0;i--){
            int left=lower_bound(P.begin(),P.end(),P[i+1]-K)-P.begin();
            res=max(res,i-left+1);
        }
        printf("%d\n",res);
        return res;
    }
};

滑动窗口代码

class Solution {
public:
    int longestOnes(vector<int>& A, int K) {
        int n = A.size();
        int left = 0, lsum = 0, rsum = 0;
        
        int ans = 0;
        for(int right=0;right<n;right++){
            rsum+=1-A[right];
            while(lsum<rsum-K){
                lsum+=1-A[left];
                left++;
            }
            ans=max(ans,right-left+1);
        }
        return ans;
    }
};