055-力扣刷题-1004--最大连续1的个数-III

给定一个由若干 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 

思路： 用双指针lo, hi维护全部是1的区间， 用 hi 线性扫描， 如果碰到0， zero += 1 如果已经有 k 个 zero 了，说明区间 左端 应该向 右 调整到跨越过一个 0 的位置。 每次循环用res记录下当前的区间最大长度。

这一个不如下面的程序简洁

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def longestOnes(self, A, k):
        """
        :type A: List[int]
        :type K: int
        :rtype: int
        """
        l = len(A) #传递近来的A的长度
        zero = 0 #记录遍历到的0的个数
        lo,hi = 0,0 #lo是需要移动的指针,窗口长度就是hi-lo+1 
        res = 0 #这个记录的是最大的长度
        for hi in range(l): #进行循环
            if A[hi] == 0: #开始遍历,如果遍历到了0就加1
                zero += 1
            while zero > k:  #当zero的个数超过k的个数的时候就要移动 lo 的坐标,直到移动到lo指向中间0位置的倒数第二个(接下来再去找更长的长度,前面的长度已经确定了)
                if A[lo] == 0: # 
                    zero -= 1 #这里lo开始移动到中间的0的位置了,移动一个就减掉一个
                lo += 1 # 移动起始的指针
            # print lo, hi
            res = max(res, hi - lo + 1) #求移动过程中的最大值


        return res #返回最大值