LeetCode1004.Max Consecutive Ones III（最大连续1的个数 III）

Description

Given an array A of 0s and 1s, we may change up to K values from 0 to 1.

Return the length of the longest (contiguous) subarray that contains only 1s.

---

给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。

返回仅包含 1 的最长（连续）子数组的长度。

题目链接：https://leetcode.com/problems/max-consecutive-ones-iii/

个人主页：http://redtongue.cn or https://redtongue.github.io/

Difficulty: medium

Example 1:

Input: A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
Output: 6
Explanation: 
[1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1.  The longest subarray is underlined.

Example 2:

Input: A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
Output: 10
Explanation: 
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1.  The longest subarray is underlined.

Note:

• 1 <= A.length <= 20000
• 0 <= K <= A.length
• A[i] is 0 or 1

分析

• 压缩A，遍历A，存储每一部分0或1的个数，形如例一：li=[(1,3),(0,3),(1,4),(0,1)];
• 从前往后遍历，得到包含最多1部分的组合，其中0部分的长度要小于K；
• 记录每一次遍历得到的最大长度（即1的长度加上可变换的0的长度）；
• 可变换0的长度是min（K，当前连续段中0的最大个数（1部分中间的0加上两端的0））
• 返回最大长度；
• 注意，不能直接返回1部分的长度加K，其中的0可能没有这么多。

参考代码

class Solution(object):
def longestOnes(self, A, K):
    li=[]
    index=A[0]
    s=0
    for a in A:
        if(a==index):
            s+=1
        else:
            li.append((index,s))
            s=1
            index=a
    li.append((index,s))
    if(len(li)==1):
        return K
    index = 0
    if(li[0][0]==0):
        index=1
    s=0
    Max=0
    for i in range(index,len(li),2):
        j=i
        s=li[i][1]
        k=0
        j+=2
        while(j<len(li) and (k+li[j-1][1])<=K):
            s+=li[j][1]
            k+=li[j-1][1]
            j+=2
        ok=0
        if(i>=1):
            ok+=li[i-1][1]
        if(j-1<len(li)):
            ok+=li[j-1][1]
        mid=min(K-k,ok)
        kk=k+mid
        Max=max((s+kk),Max)
    return Max