每日算法系列【LeetCode 1004】最大连续1的个数 III

关注公众号【算法码上来】,每日算法干货马上就来!

题目描述

给定一个由若干 0 和 1 组成的数组 A ,我们最多可以将 K 个值从 0 变成 1 。

返回仅包含 1 的最长(连续)子数组的长度。

示例1

输入:
A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出:
6
解释:
[1,1,1,0,0,1,1,1,1,1,1]
A[5] 和 A[10] 从 0 翻转到 1,最长的子数组长度为 6。

示例2

输入:
A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出:
10
解释:
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
A[4] 、A[5] 和 A[9] 从 0 翻转到 1,最长的子数组长度为 10。

提示

  • 1 <= A.length <= 20000
  • 0 <= K <= A.length
  • A[i] 为 0 或 1

题解

这题可以采用滑动窗口方法来求解。
也就是用头尾指针 l 和 r ,初始化都是 l = r = 0 ,然后向右移动指针 r 。
用变量 cnt0 记录 [l, r] 区间内有几个 0 ,用 res 保存答案。

如果 A[r] = 0 ,那就 0 的数量 cnt0 加 1 。
并且 0 的数量和 K 判断,如果 cnt0 <= K ,那就说明 [l, r] 中间的 0 不多,可以用至多 K 次机会填充,那就继续向右移动 r 。
但是如果 cnt0 > K ,那就说明 0 的数量太多了,得删掉点 0 了,这时候就得向右移动 l 。
这时候看情况,如果 A[l] = 0 ,就要减小 cnt0 ,直到 cnt0 <= K 为止,不再移动 l 。
然后继续移动 r ,重复上面过程即可。过程中时刻更新最长的距离 res 。

因为 l 和 r 分别最多移动 n 次,所以最终的时间复杂度是 $O(n)$ 的。

那么为什么这样是正确的呢?不会漏掉正确答案所在的区间吗?
我们看看漏掉的是哪些区间。
对于一个固定的 r ,移动 l 直到 0 的数量小于等于 K (记为 l’ )的过程中,漏掉的是 [<l, r] 和 [>l’, r] 这些区间。
前者 0 数量太多,不符合题意;后者长度更小,显然不是答案。
然后继续右移 r ,直到第一个 0 数量大于 K 的位置,漏掉了 [<l, >r] 和 [>l, >r] 区间。
前者 0 的数量一定大于 K ,为什么呢?因为右端点在 r 的时候, l 已经是最靠左使得 0 数量小于等于 K 的位置了,而现在 r 向右移动了, l 更不可能左移了;后者长度更小,不予考虑。
综上考虑,最优的区间一定被考虑充分了。

代码

class Solution {
public:
    int longestOnes(vector<int>& A, int K) {
        int n = A.size();
        int l = 0, r = 0, cnt0 = 0, res = 0;
        while (r < n) {
            if (!A[r]) {
                cnt0++;
                while (cnt0 > K && l <= r) {
                    if (!A[l++]) cnt0--;
                }
            }
            res = max(res, r - l + 1);
            r++;
        }
        return res;
    }
};

   转载规则


《每日算法系列【LeetCode 1004】最大连续1的个数 III》 韦阳 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
每日算法系列【LeetCode 1250】检查「好数组」 每日算法系列【LeetCode 1250】检查「好数组」
关注公众号【算法码上来】,每日算法干货马上就来! 题目描述给你一个正整数数组 nums ,你需要从中任选一些子集,然后将子集中每一个数乘以一个任意整数,并求出他们的和。 假如该和结果为 1 ,那么原数组就是一个「好数组」,则返回 Tr
2020-01-10
下一篇 
论文赏析【EMNLP19】语言模型效果不好?也许你可以给它添加一点句法信息 论文赏析【EMNLP19】语言模型效果不好?也许你可以给它添加一点句法信息
关注公众号【算法码上来】,每日算法干货马上就来! 论文地址PaLM: A Hybrid Parser and Language Model 介绍本文介绍了如何将一个句法分析器融入到神经网络语言模型中,这样在利用了句法信息增强语言模型效
2020-01-09
  目录