leetcode 1004 Max Consecutive Ones III

1.题目描述

给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。
返回仅包含 1 的最长（连续）子数组的长度。

示例 1：
输入：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：
[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。
示例 2：
输入：A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。

提示：
1 <= A.length <= 20000
0 <= K <= A.length
A[i] 为 0 或 1

2.解题思路

滑动窗口，维护两个指针。窗口向右滑动时候判断如果其中0的个数小于K，左指针不变右指针向右滑动，反之右指针不变左指针向右滑动。可以通过判断滑动的边缘数字来判断0的增减以减小复杂度。

3.Python代码

class Solution(object):
    def longestOnes(self, A, K):
        """
        :type A: List[int]
        :type K: int
        :rtype: int
        """
        A.append(2)
        left,res,right=0,0,1
        c=A[left:right].count(0)
        while right<len(A):
            if c<=K:
                res=right-left if right-left>res else res
                if A[right]==0:
                    c+=1
                right+=1
            else:
                if A[left]==0:
                    c-=1
                left+=1
        return (res)