原题链接

题目描述：

给你一个01字符串，定义答案=该串中最长的连续1的长度，现在你有至多K次机会，每次机会可以将串中的某个0改成1，现在问最大的可能答案

输入描述:

输入第一行两个整数N,K，表示字符串长度和机会次数(1 <= N <= 300000, 0 <= K <= N) 第二行输入N个整数，表示该字符串的元素。

输出描述:

输出一行表示答案

示例1

输入

10 2 
1 0 0 1 0 1 0 1 0 1

输出

5

方法一 动态规划

本题是属于简单的一维动态规划，首先我们需要搞清楚的是，题目要求的最长的全1串是通过将最多K个0改成1后得到的。

如果字符串中的0的数量不超过K, 那么答案就是字符串的长度，因为我们可以把所有的0修改成1。

如果0的数量超过了K，那我们怎么修改得到结果呢？ 答案是：我们一定要修改隐藏1后的串中连续K个0才可能出现要求的最长全1串。

简单证明一下： 必须连续K个0，如果不连续，那么中间会有0断开全1串，那么一定不会大于修改连续K个0的结果。 必须是K，如果修改不到K次，那么一定不会大于修改K次的结果。

综上，我们的思路就很清晰了。 对于示例1

01串的位置：0 1 2 3 4 5 6 7 8 9
隐藏1后0串：  0 0   0   0   0
01原字符串：1 0 0 1 0 1 0 1 0 1

用f[x]记录第x个0在串中的位置。

f[1]=1, f[2]=2, f[3]=4, f[4]=6, f[5]=8

下标 i 遍历 01 串区间 [0, N)，如果当前的 0 的数量 x 不大于 K ，那么以位置 i 结尾的最长的全1串长度为 i + 1。

如果当前0的数量x超过K，那么以位置i结尾得到的最长全1串的长度，就是我们从i向前修改连续K个0后的结果，长度为：当前位置i - 第 x-K 个0在串中的位置 即 i - f[x-K]，我们用ans不断更新这两个结果，最后遍历结束就是最终的答案。

AC代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300000 + 1;
int f[MAXN], ans = 0;

int main() {
    int N, K, num, count = 0;
    
    scanf("%d%d", &N, &K);
    
    for(int i = 0; i < N; ++i) {
        scanf("%d", &num);
        if(num == 0) f[++count] = i;       
        if(count <= K) ans = max(i+1, ans);
        else  ans = max(i - f[count - K], ans);
    }
    
    printf("%d", ans);
    return 0;
}

复杂度

  • 时间复杂度：O(N)O(N)
  • 空间复杂度：O(N)O(N)

方法二 双指针

由于本题特殊性，可以用双指针来解，具体的，两个指针维护中间 0 个数，右指针每次右移一步。当中间 0 个数超过 k 时候，左指针向右移动一次。最后两个指针的距离就是最长全 1 串长度。

AC代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300000 + 1;
int num[MAXN];

int main() {
    int N, K;
    
    scanf("%d%d", &N, &K);

    int i, j, con = 0;
    for(i = 0, j = 0; i < N; ++i) {
        scanf("%d", &num[i]);
        if(!num[i]) ++con;
        if(con > K && !num[j++]) --con;
    }
    
    printf("%d", i-j);    
    return 0;
}

复杂度

  • 时间复杂度：O(N)O(N)
  • 空间复杂度：O(N)O(N)