1004.md

Max Consecutive Ones III

Description

link

---

Solution

• 右边保持滑动，左边保存两个变量l，r分别代表从l，r到右边区间内存在K个以及K-1个不同整数的区间
• 此时答案即为加上r-l即可

---

Code

O(n) O(n)

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        res = 0
        l = 0
        for r in range(len(A)):
            if K >= 0:
                res = max(res, r - l)
            if A[r]: continue
            K -= 1
            while K < 0:
                while A[l]: l += 1
                K += 1
                l += 1
        if K >= 0: res = max(res, r - l + 1)
        return res