题意：

给你一个长度为 $n$ 的01数组，你可以将其中 $m$ 个数字0变成数字1，问变化后数组中最长连续的一段1长度是多少？

解法一（暴力求解，不可AC）

首先我们可以枚举数组中每一个数，当枚举到第 $i$ 个数时，我们可以暴力求出以第 $i$ 个数为结尾，最长的连续一段1长度的值，我们记其为第 $i$ 个数对答案的贡献

最终答案即为所有贡献的最大值

具体的：

对于第 $i$ 个数字，我们可以暴力往前循环，若遇到0，则将 $m$ 减一；若遇到1，则继续向前，直到无法向前或者 $m$ 为0则结束循环

最后对于第 $i$ 个数字的贡献即为遇到数字的总个数

（注意每次 $m$ 要恢复为原来的值）

代码：

class Solution {
public:
    int solve(int n, int m, vector<int>& a) {
        int ans=0;//最终答案
        for(int i=0;i<n;i++){
            int t=m;//临时存储m
            int c=0;//遇到的数字个数
            for(int j=i;j>=0&&t>0;j--){
                c++;//数字个数+1
                if(a[j]==0)t--;//消耗一次变1的机会
            }
            ans=max(ans,c);//答案取最大值
        }
        return ans;
    }
};

时间复杂度： $O(n^2)$ ，枚举每一个数字的代价是 $O(n)$ 的，对于每一个数字，往前循环计算贡献的代价也是 $O(n)$ 的，故总的时间复杂度是 $O(n^2)$

空间复杂度： $O(n)$ ，程序中需要存储 $n$ 个整型数字和若干个整型变量，故空间复杂度为 $O(n)$

解法二（队列优化）

在解法一中，程序主要的时间瓶颈是对于每个数字计算贡献需要 $O(n)$ 的时间

我们同样是考虑计算以第 $i$ 个数为结尾，最长的连续一段1长度的值

我们考虑解法一中往前枚举将0变成1的过程，0的位置一定是距离当前位置最近的 $m$ 个0所在的位置，这 $m$ 个位置我们可以用一个大小为 $m$ 的队列来维护

例如下图所示的例子：

我们设 $f[i]$ 表示以第 $i$ 个元素为结尾，最长的连续的1的长度，显然有：

$a[i]==1:f[i]=f[i-1]+1\\ a[i]==0:f[i]=0$

我们设 $g[i]$ 表示若第 $i$ 个数字为1，以第 $i$ 个元素为结尾，最长的连续的1的长度，显然有：

$a[i]==1:g[i]=f[i]\\ a[i]==0:g[i]=f[i-1]+1$

我们假设队头元素为 $x$ ，显然由于队列存储的是距离当前位置最近的 $m$ 个0所在的位置，则 $x$ 后面的0一定变成了1，则当前以第 $i$ 个数为结尾，最长的连续一段1长度的值为 $i-x+g[x]$

于是我们只需要预处理出 $f,g$ 数组，然后在枚举每一个数字的过程中维护上述队列即可，最后答案即为最大的以第 $i$ 个数为结尾，最长的连续一段1长度的值

代码：

class Solution {
public:
    int f[1000000];//以第i个元素为结尾，最长的连续的1的长度
    int g[1000000];//若第i个元素为1，最长的连续的1的长度
    int solve(int n, int m, vector<int>& a) {
        memset(f,0,sizeof f);
        memset(g,0,sizeof g);//多测清空
        f[0]=a[0];
        g[0]=1;
        for(int i=1;i<a.size();i++){
            if(a[i]){
                f[i]=f[i-1]+a[i];
            }else{
                f[i]=0;
            }
            g[i]=max(f[i],f[i-1]+1);
        }
        queue<int> que;
        int ans=a[0];//表示最终答案
        for(int i=1;i<n;i++){
            if(!a[i]){
                //若当前数字为0
                if(que.size()==m)que.pop();//队列大小最大只能为m
                que.push(i);
                if(m>1){
                    ans=max(ans,i-que.front()+g[que.front()]);
                }else{
                    //若只能改变一个0，则当前位置对答案的贡献为g[i]
                    ans=max(ans,g[i]);
                }
            }else{
                if(que.size()>0){
                    ans=max(ans,i-que.front()+g[que.front()]);
                }else{
                    ans=max(ans,f[i]);
                }
            }
        }
        return ans;//返回答案
    }
};

时间复杂度： $O(n)$ ，我们预处理出 $f,g$ 数组的代价是 $O(n)$ ，枚举每一个数字的代价是 $O(n)$ 的，由于每一个元素最多只会进出队列一次，故维护队列的复杂度为 $O(n)$ ，求解每一个位置的贡献的代价为 $O(1)$ ，故总的时间复杂度为 $O(n)$
空间复杂度： $O(n+m)$ ， $f,g$ 数组的都是占 $O(n)$ 级别的内存，队列的大小最多为 $m$ ，故总的空间复杂度为 $O(n+m)$

题解 | #牛牛的木板#

题意：

解法一（暴力求解，不可AC）

解法二（队列优化）