标签搜索

目 录CONTENT

文章目录

美团--最长全1串.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 3 阅读 / 2,097 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

美团--最长全1串

@[toc]

一、问题描述

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

  •  输入描述:
输入第一行两个整数N,K,表示字符串长度和机会次数

第二行输入N个整数,表示该字符串的元素

( 1 <= N <= 300000
, 0 <= K <= N )
  •  输出描述:
输出一行表示答案

输入例子1:
10 2 
1 0 0 1 0 1 0 1 0 1

输出例子1:
5

二、分析

这道题和很多题类似:

这几道题基本上是一样的,这道题也是:力扣1004. 最大连续1的个数 III:最大连续1的个数

  •  首先考虑本问题的最直观朴素的想法:枚举出每一个子串,逐个验证其有效性并且更新最大值。
  •  这种做法的时间复杂度是O(n^3),在这一数据规模下是一定会超时的,超时的原因是做了非常多重复的验证计算,且枚举了非常多没有意义的串
  •  那么基于我们在这类连续子数组性质问题的经验,使用双指针(滑动窗口)会是一个非常好的想法
  •  双指针解法
  •  双指针解法的重点在于维护两个指针
  •  设置两个指针(表现为数组下标值),左指针指向当前子串左边界,右指针指向当前子串右边界,我们通过某种方法使得左右指针之间的当前子串符合要求:即 '0' 的数目小于等于 K
  •  又:我们很容易知道,最长串一定出现在串内 '0' 的数目饱和(如果'0'比较多)或者最大(如果 K 比较大)的情况下,因此我们需要尽可能地把右指针右移
  •  那么固定左指针时,什么情况下可以使右指针右移呢?转化次数K有剩余 或右指针的下一位是'1'
  •  如此移动右指针,即可找到每一个左指针所对应的最长有效串,而且右指针指向的元素的下一位一定是'0'
  •  那么我们可以把每一个数组元素作为左指针,以上述方式枚举出最长有效串,然后返回结果
  •  但是还是不够快
  •  不够快的原因还是做了重复计算,在左指针变化时,右指针从左指针处开始右移,没有有效利用上一次操作的结果,造成了大量没有必要的操作;那么如何避免重复计算呢?
  •  我们的关键在于刚刚提到的“0数饱和”。即:可能成为最长串的串,它内部'0'的数量一定是饱和或者最大的
  •  那么我们可以通过某种操作来使得在左指针右移之后,我们立即就能获得新左指针对应的'0'数饱和串/'0'数最大串
  •  首先我们考察左指针右移一位时的情况:
  •  首先我们需要清楚一个事实:当右指针到达串尾部时,左指针没有任何必要继续右移,因为左指针右移的话子串的长度一定会减小,并且饱和性质无法保证
  •  也就是说,左指针右移的条件是:右指针没有触碰串的右边界
  •  那么我们会得到一个推论:当左指针需要右移时,串中的'0'一定是饱和的而不是最大的(“饱和”指子串中0的数目与K相等,不可以再转化0为1;“最大”指整个串中所有的0均已被转化为1)既饱和又最大的情况也不需要右移
  •  得到这个推论,我们就可以来考虑左指针右移时的情况:
  •  当前左指针指向的元素是'0'时:当左指针右移时子串内的'0'数减一为了维护其饱和性质,我们刚刚提到“右指针指向的元素的下一位一定是'0'”,所以右指针一定可以右移至少一位(如果右移之后的下一位是'1'则可以继续右移)
  •  当前左指针指向的元素是'1'时:当左指针右移时子串内的'0'数不变,由于我们维护了每一个子串的饱和性质,右指针不可以右移
  •  每一次左指针移动及之后右指针移动的一系列操作结束之后,更新最大值。通过以上的操作,遍历直到右指针触碰数组右边界,即可得到全局的最大符合条件串的长度
  •  开销分析
  • 平均渐进时间复杂度O(n)
  • 渐近额外空间O(1)

三、代码

class Solution {
public:
    int longestOnes(vector<int>& A, int K) {
    	//在这个实现中,right指的是当前子串末尾的下一位
        int left(0), right(0);
        int max(0);
        
        while (left <= right && right < A.size()) 
        {
        	//如果right没有走到结尾,并且right位置为1(可以直接++)或者
        	//right位置为0(如果k不等于0)那么可以进行一次0-》1转变,
        	//继续++)
            while (right < A.size() && (A[right] || K != 0)) 
            {
            	//如果是0,那么k的值需要--
                if (!A[right]) 
                	K--;
                right++;
            }
            //更新结果
            max = std::max(right - left, max);

			//如果left位置为1,只需要left++
            if (A[left]) 
            	left++;
            //反之代表left位置为0,那么我们需要同时++
            else 
            {
            	left++, 
            	right++;
            }
        }
        return max;
    }
};
0

评论区