题目描述

牛牛从牛毕那里拿了一根长度为n的白木板，木板被等分成了n段，其中有些段被牛毕用颜料染成了黑色。
牛牛对木板进行清洗，但是最多只能清洗m段。
牛牛想知道，它足够聪明地清洗木板，能获得的纯白色木板的最大长度是多少。
示例1
输入：6,1, [1,0,0,1,1,1]
返回值：4
说明：染成了[1,0,1,1,1,1]

题目分析

题目的意思为，用0表示黑色，1表示白色，可以通过m次变化，将0变为1，求能够获取最长的连续1的长度。

我们可以将所有0位置的下标记录在black[]数组中，要想获得最长的连续长度，则这m个变化的0在black中一定是连续的，可以遍历black中所有连续m个0的长度：black[i+m]-black[i-1]-1，找出其中的最大值。
如下图，需要在black数组中增加两个0，第一个0的下标是-1，最后一个0的下标是n，是为了能够统计数组中所有的1（包括最开始和最后的1）
图片说明

解题思路

方法1：使用数组记录0的位置，遍历修改m个0的所有情况，记录连续的1的个数
1.初始化一个数组black[]，存储0的位置，可以先遍历一遍数组，求出0的总个数，也可以直接设置成n+2，再使用一个变量total统计当前0的总个数；
2.在遍历数组的过程中，当a[i]==0时，记录0的个数和下标，只要total不超过m个，那从0到i的位置都可以是连续的1（是0的都可以变成1）；
3.当total超过了m个，那需要减去最前面的一个0的位置；
4.遍历记录出现的最长的长度。

方法2：双指针遍历数组
当数据要求必须是连续的时候，可以使用滑动窗口来实现，滑动窗口的基本思路如下：

 // 定义窗口左右指针
 int left,right;
  while(遍历数组){
     if(满足条件){
          // 右指针先走
          right++;
     }
     while(不满足条件){
         // 左指针后走，直到符合条件
         left++;
     }
     //right-left+1是窗口的的长度
  }

这里要满足的条件就是左右指针中间的0的个数不能超过m个，所以使用一个变量length来记录中间0的个数。

代码实现

方法1：使用数组记录0的位置，遍历修改m个0的所有情况，记录连续的1的个数

public int solve (int n, int m, int[] a) {
    // 记录黑色部分0的位置数组，最多为n，再加上两个0的位置
    int[] black = new int[n+2];
    // 记录黑色部分总数
    int total = 0;
    // 最长的连续1的长度
    int res = 0;
    // 初始化第一个0的位置为-1，为了包含数组中前面的1
    black[0] = -1;
    for(int i=0;i<n;i++){
       if(a[i] == 0){
            total++;
            black[total] = i;
       }
       int length = 0;
       if(total > m){
            // 只能到限制的前m个零的位置
           length = i-black[total-m];
       }else{
            // 否则可以从头计算
           length = i-black[0];
       }
       res = Math.max(res, length);
    }
    return res;
}

时间复杂度：，需要遍历整个数组，时间花费为n；
空间复杂度：，需要额外使用记录黑色位置的数组，数组长度为n+1；

方法2：双指针遍历数组

public int solve (int n, int m, int[] a) {
    // 存储最长结果
    int res = 0;
    // 记录0的个数
    int length = 0;
    // 记录左边界位置
    int l = 0;
    // 右边界位置不断移动
    for(int r=0;r<n;r++){
        if(a[r] == 0){
            // 碰到了0，增加length
           length++;
        }
        // 当0的个数超过限制m个，则不断移动左边界直到个数不超过m（等于m）
        while(length > m){
           // 移动左指针到区间左边第一个零的位置
           if(a[l] == 0){
               length--;
           }
           l++;
        }
        // 当前窗口的长度即为最长连续1的长度
        res = Math.max(res, r-l+1);
    }
    return res;
}

时间复杂度：，滑动窗口的左右指针一直都在向前进，不会后退，时间花费是左指针和右指针走的步数之和，时间最多花费2n；
空间复杂度：，只需要常数级的空间。