1004._Max_Consecutive_Ones_III.md

1004. Max Consecutive Ones III

难度: 中等

刷题内容

原题连接

• https://leetcode.com/problems/max-consecutive-ones-iii/

内容描述

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. 

 

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 

解题方案

思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(1)******

双指针法

左指针left，右指针right，[left, right]双闭区间表示一个经过一定次数的翻转后已经全部是1的区间，这个区间的最大长度就是我们要求的长度；

变量zeros统计该区间内的被翻转的0的个数，zeros <= K；

变量ones保存最大区间长度；

left和right的起始位置都设定为0，我们每次都向右移动一次right指针代表新判断一个元素。此时，如果right指向的数字是0，我们需要将zero+1，代表我们把这个0进行了翻转。当zeros > K时，则移动left指针，left指针有可能指向了1，所以需要一直移动直至zeros <= K为止。

beats 77.5%

class Solution(object):
    def longestOnes(self, A, K):
        """
        :type A: List[int]
        :type K: int
        :rtype: int
        """
        zeros = 0
        ones = 0
        left = 0
        for right, value in enumerate(A):
            if value == 0:
                zeros += 1
            while zeros > K:
                if A[left] == 0:
                    zeros -= 1
                left += 1
            ones = max(ones, right - left + 1)
        return ones

思路 2 - 时间复杂度: O(N^2)- 空间复杂度: O(1)******

穷举法

跟思路1类似，当翻转次数K用完后，头部继续向前移动，当遇到一个0，则记录当前的长度和舍弃尾部一个0，如此循环下去，最后得到最大长度。

class Solution:
    def longestOnes(self, A, K):
        Z = K
        now_l = 0
        max_l = 0
        for i in range(len(A)):
            if A[i] == 1:
                now_l = now_l + 1
            elif K >= 1:
                K = K - 1
                now_l = now_l + 1
            else:
                if now_l > max_l:
                    max_l = now_l
                if Z > 0:
                    for j in range(i-now_l, i):
                        if A[j] == 0:
                            now_l = i - j
                            break
                else:
                    now_l = 0
        return max(max_l, now_l)