LeetCode题解:1004. 最大连续1的个数 III 木灵的炼金工作室

题目描述

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

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

输入:A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出:6

解题思路

首先考虑本问题的最直观朴素的想法:枚举出每一个子串,逐个验证其有效性并且更新最大值 这种做法的时间复杂度是O(n^3),在这一数据规模下是一定会超时的 超时的原因是做了非常多重复的验证计算,且枚举了非常多没有意义的串 那么基于我们在这类连续子数组最值性质问题的经验,使用双指针(滑动窗口)会是一个非常好的想法

双指针解法

双指针解法的重点在于维护两个指针: 设置两个指针(表现为数组下标值),左指针指向当前子串左边界,右指针指向当前子串右边界,我们通过某种方法使得左右指针之间的当前子串符合要求:即 '0' 的数目小于等于 K 又:我们很容易知道,最长串一定出现在串内 '0' 的数目饱和(如果'0'比较多)或者最大(如果 K 比较大)的情况下,因此我们需要尽可能地把右指针右移

那么固定左指针时,什么情况下可以使右指针右移呢?

  • 转化次数K有剩余 或
  • 右指针的下一位是'1'

如此移动右指针,即可找到每一个左指针所对应的最长有效串,而且右指针指向的元素的下一位一定是’0’ 那么我们可以把每一个数组元素作为左指针,以上述方式枚举出最长有效串,然后返回结果

但是还是不够快

不够快的原因还是做了重复计算,在左指针变化时,右指针从左指针处开始右移,没有有效利用上一次操作的结果,造成了大量没有必要的操作 那么如何避免重复计算呢?

我们的关键在于刚刚提到的“0数饱和”

即:可能成为最长串的串,它内部'0'的数量一定是饱和或者最大的 那么我们可以通过某种操作来使得在左指针右移之后,我们立即就能获得新左指针对应的'0'数饱和串/'0'数最大串

首先我们考察左指针右移一位时的情况: 首先我们需要清楚一个事实:当右指针到达串尾部时,左指针没有任何必要继续右移,因为左指针右移的话子串的长度一定会减小,并且饱和性质无法保证 也就是说,左指针右移的条件是:右指针没有触碰串的右边界 那么我们会得到一个推论:当左指针需要右移时,串中的'0'一定是饱和的而不是最大的(“饱和”指子串中0的数目与K相等,不可以再转化01;“最大”指整个串中所有的0均已被转化为1既饱和又最大的情况也不需要右移

得到这个推论,我们就可以来考虑左指针右移时的情况:

  1. 当前左指针指向的元素是'0'时:当左指针右移时子串内的'0'数减一,为了维护其饱和性质,我们刚刚提到“右指针指向的元素的下一位一定是'0'”,所以右指针一定可以右移至少一位(如果右移之后的下一位是'1'则可以继续右移)
  2. 当前左指针指向的元素是'1'时:当左指针右移时子串内的'0'数不变,由于我们维护了每一个子串的饱和性质,右指针不可以右移

每一次左指针移动及之后右指针移动的一系列操作结束之后,更新最大值 通过以上的操作,遍历直到右指针触碰数组右边界,即可得到全局的最大符合条件串的长度

开销分析

平均渐进时间复杂度O(n) 渐近额外空间O(1)

代码

在这个实现中,right指的是当前子串末尾的下一位

//天知いのり 2020.5.24
class Solution {
public:
    int longestOnes(vector<int>& A, int K) {
        int left(0), right(0);
        int max(0);
        while (left <= right && right < A.size()) {
            while (right < A.size() && (A[right] || K != 0)) {
                if (!A[right]) K--;
                right++;
            }
            max = std::max(right - left, max);
            if (A[left]) left++;
            else left++, right++;
        }
        return max;
    }
};


Copyright AmachiInori 2017-2021. All Right Reserved.
Powered By Jekyll.
amachi.com.cn