---
# System prepended metadata

title: 1004. Max Consecutive Ones III
tags: ['1004', leetcode, sliding window, medium, rewrite]

---

# 1004. Max Consecutive Ones III

###### tags: `leetcode` `sliding window` `1004` `medium` `rewrite` 

## :memo:  Question
![](https://i.imgur.com/wWCaA2T.png)


## :memo: 題意
:bulb: 給你一組 numslist & k，numslist 是由 0 和 1 組成的，問你你可以翻轉 0 成 1 k 次，那最長的連續的 1 的 list 最長是多少？



## :memo: leetcode solution
* :medal: **思考一**: 用 sliding window，可以想到用 sliding window 就差不多解完題目了。

```python=
nums = [1,1,1,0,0,0,1,1,1,1,0]
k = 2
# pseudo code
# 1. use sliding window and set l & r point to traverse the nums
# 2. record maxcount & flipcount
# 
# if met the 1:
#      r point keep going，
#      r += 1
#.     count += 1
#      maxcount = max(count, maxcount)
# elif met the 0:
#     if flipcount <= k:
#.         r point keep going
#          r += 1
#          count += 1     
#          maxcount = max(count, maxcount)
#     else: 
#         l point step to forward to flpcount <= k:

```



```python=
class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        
        l = 0
        r = 0
        maxcount = 0
        flipcount = 0
        count = 0
        
        while r < len(nums):
            if nums[r] == 1:
                # r += 1
                count += 1
                maxcount = max(count, maxcount)
            else:
                flipcount += 1
                if flipcount <= k:
                    # r += 1
                    count += 1
                    maxcount = max(count, maxcount)
                else:
                    while flipcount > k:
                        if nums[l] == 1:
                            l += 1
                        else:
                            l += 1
                            flipcount -= 1
                            count = r - l + 1
            r += 1
            
        return max(maxcount, count)
```

## :memo: bigO
* 時間複雜度: O(2n)
* 空間複雜度: O(1)

## :-1: **檢討**
* 程式第28行，count = r - l + 1，這邊要注意小心