---
# System prepended metadata

title: 1004. Max Consecutive Ones III
tags: [LeetCode75, Sliding Window, medium, important]

---

給一串二元陣列 和 可以翻轉K次0變成1的常數 在翻轉次數內形成可能的最長連續1
 
思考
1.用窗格的方式計算 但這題的窗格SIZE為不固定
2.窗格的條件是 此窗格內的0 還足夠翻轉次數
3.如果下一次遇到零 但翻轉次數已經用完? 右移窗格的左指標 把翻轉次數空出來
4.計算每一次成立窗格的連續1長度 並且更新最大值 (右邊界 - 左邊界 + 1)
  
```C++=
class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        //窗格的成立條件 
        //維護一個窗格內0的數量
        //窗格大小為不固定 根據維護增大縮小
        //回傳當前連續1的值 更新最大
        int maxV = INT_MIN;
        //指向左邊界
        int i = 0;
        //指向右邊界
        int j = 0;
        //紀錄窗格內有幾個0
        int count = 0;
        while(j < nums.size()){
            if(nums[j] == 0){
                //如果窗格內是0
                count++;
            }
            while(count > k){
                //如果已經把轉零的次數用光了 則把左指標移動到0上
                if(nums[i] == 0){
                    count--;
                }
                i++;
            }
            //窗格內1的連續數目 因為保持窗格內的0都能反轉 所以一定都是連續
            maxV = max(maxV, j - i + 1);
            j++;
        }
        return maxV;
    }
};
```


```c++=
class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        //記錄並維持一個窗格內的0次數
        //窗格要有頭尾
        int left = 0;
        int right = 0;
        //紀錄翻轉幾次
        int count = 0;
        //紀錄長度
        int maxV = INT_MIN;
        while(right < nums.size()){
            //有掃到0則翻
            if(nums[right] == 0){
                count++;
            }
            while(count > k){
                //超過翻轉次數要回復次數 要找到left是0並且往前一格
                if(nums[left] == 0){
                    count--;
                }
                //找到0後還會往前一格
                left++;
            }
            //更新長度
            maxV =  max(maxV, right - left +1 );
            //進入下一輪
            right++;
        }
        return maxV;
    }
};

```

```c++=
class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        //維持窗格內 翻轉操作的次數
        //更新最大數目
        //如果超過可使用操作的次數要回復次數
        int left = 0;
        int right = 0;
        int count = 0;
        int maxV = INT_MIN;
        while(right < nums.size()){
            if(nums[right] == 0 ){
                //使用操作
                count++;
            }
            //如果操作次數使用到達限制要回復
            while(count > k){
                //找到 0 回復操作 並移動left
                if(nums[left] == 0){
                    count--;
                }
                left++;
            }
            //計算長度
            maxV = max(maxV, right - left +1);
            right++;
        }
        return maxV;
    }
};

```

```c++=
class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int left = 0;
        int right = 0;
        int count = 0;
        int ans = INT_MIN;
        while(right < nums.size()){
            if(nums[right] == 0){
                count++;
            }
            if(count > k){
                //超過回復次數了
                while(nums[left] != 0){
                    left++;
                }
                count--;
                left++;
            }
            ans = max(ans, (right - left + 1));
            right++;
        }
        return ans;
    }
};

```