一.題目描述

最大連續(xù)1的個(gè)數(shù)

?這道題要我們找最大連續(xù)1的個(gè)數(shù)，看到“連續(xù)”二字，我們要想到滑動(dòng)窗口的方法?；瑒?dòng)窗口的研究對(duì)象是一個(gè)連續(xù)的區(qū)間，這個(gè)區(qū)間需要滿足某個(gè)條件。那么本題要找的是怎樣的區(qū)間呢？是一個(gè)通過翻轉(zhuǎn)0后得到連續(xù)1的區(qū)間，而最多可以翻轉(zhuǎn)k個(gè)字符。

故要找的是包含0的個(gè)數(shù)不超過k的區(qū)間，因?yàn)槿绻^k個(gè)0，即使經(jīng)過翻轉(zhuǎn)，該區(qū)間的1也還是不連續(xù)。

題意轉(zhuǎn)化過來后，本題便不再困難。

二.思路分析

滑動(dòng)窗口是在暴力解法的基礎(chǔ)上優(yōu)化過來的。本題的暴力解法就是兩層for循環(huán)枚舉所有的區(qū)間，找出滿足條件的區(qū)間，通過比較得到最長(zhǎng)的區(qū)間長(zhǎng)度，結(jié)果就是數(shù)組中連續(xù)1的最大個(gè)數(shù)。

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int n = nums.size();int ret = 0;for (int left = 0; left < n; left++){int zero = 0;//記錄0的個(gè)數(shù)for (int right = left; right < n; right++){if (nums[right] == 0){zero++;}//如果0的個(gè)數(shù)已經(jīng)超過k,right向后枚舉的區(qū)間肯定也不符合要求if (zero > k){break;}ret = max(ret, right - left + 1);}}return ret;}
};

要想用滑動(dòng)窗口，首先要證明right沒有回退的必要

?如圖，right從left位置出發(fā)，依次向后枚舉，到圖中的位置[left, right]區(qū)間內(nèi)0的個(gè)數(shù)大于k,停了下來。這說明[left, right - 1]區(qū)間是滿足要求的。

?

按照暴力枚舉策略，left向右移動(dòng)一步，right回退到left位置。但最終right還是會(huì)回到原來的標(biāo)記處。因?yàn)橥ㄟ^上一輪枚舉，我們可知圖中大括號(hào)標(biāo)記的區(qū)間都是符合條件的，而right只有在區(qū)間不滿足要求時(shí)才會(huì)停下。所以right沒有必要回退，留在原地即可。?

?

?那么此時(shí)[left, right]區(qū)間是否符合條件呢？答案是不一定。因?yàn)榭赡躭eft跳過的是一個(gè)1, 0的數(shù)量并沒有減少，也有可能跳過了一個(gè)0，區(qū)間內(nèi)剛好有k個(gè)0。

當(dāng)區(qū)間符合條件時(shí)，我們讓right繼續(xù)向后移動(dòng)，接下來的步驟就和上面一樣了。當(dāng)區(qū)間不符合條件時(shí)，right向后枚舉的區(qū)間就更不滿足了，所以我們讓left繼續(xù)向右移動(dòng)，直到區(qū)間滿足要求為止。

故判斷應(yīng)該是一個(gè)循環(huán)語(yǔ)句，不能簡(jiǎn)單地只判斷一次。

三.代碼編寫

按照滑動(dòng)窗口的模版，找到各個(gè)條件即可。當(dāng)枚舉的情況滿足要求時(shí)應(yīng)該更新結(jié)果。什么時(shí)候滿足要求呢？

1.進(jìn)窗口之后，zero>=k,符合要求

2.進(jìn)窗口之后，zero<k,經(jīng)過若干次出窗口操作后，zero=k ，滿足要求

故更新結(jié)果應(yīng)放在整個(gè)循環(huán)的最后面

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int n =nums.size();int zero = 0;//記錄窗口內(nèi)0的個(gè)數(shù)int left = 0, right = 0;int ret = 0;while (right < n){//進(jìn)窗口if (nums[right] == 0){zero++;}//判斷while (zero > k){//出窗口if (nums[left] == 0){zero--;}left++;}//更新結(jié)果ret = max(ret, right - left + 1);right++;}return ret;}
};

時(shí)間復(fù)雜度O(n)，相比于暴力枚舉的O(n^2)提升了不少。