LeetCode-1004.最大连续1的个数 III(Max Consecutive Ones III) 题解
Leetcode-1004(力扣-1004)
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
题目描述
给定一个数组，其中只包含0或者1。可以把数组中的元素从0变到1，或者从1变到0，一次变换的操作称作一次翻转。给出K，对数组做最多K次的翻转，使数组中连续的1出现的长度最长。
优秀题解(参考：Leetcode-1004-max-consecutive-ones-iii-Discuss)
def longestOnes(self, A, K):
i = 0 # i代表窗口左侧。
for j in xrange(len(A)): # j代表窗口右侧，j一直在增大
K -= 1 - A[j] # K用于控制窗口是否需要压缩
if K < 0:
K += 1 - A[i]
i += 1 # 当K<0时，窗口压缩(i增加)
return j - i + 1 # 返回窗口的最终长度
优秀题解分析
该算法复杂度是O(N)。
分析思路：
基于数组构建一个动态滑动窗口(后续简称窗口)。窗口长度即为所求连续1的最大长度。可以认为初始状态，窗口左侧边界和右侧边界的index均为0，窗口的长度为0。随后，窗口开始向右拉伸，拉伸持续进行，而收缩只在特定条件下发生，直到窗口右侧到达数组的最后一个元素，即可求出最大长度。窗口在滑动过程中，有以下2个状态：
-
拉伸态：窗口左侧保持不变，右侧向右滑动。(当给定参数K>0时，可以认为刚开始就是这种状态) 在拉伸时，经过K次翻转，将拉伸时遇到的0翻成1，此时K=0。(如果数组中的0的数目小于K，那么数组的长度即为所求的解，直接返回)由于在拉伸时，遇到1对K没有影响，那么直接当K==0时，窗口的长度即为当前连续1的最大长度。
-
收缩态：窗口左测和右侧均向右滑动。收缩态，指的是窗口左侧向右滑动，由于窗口右侧一直在向右滑动，所以该状态窗口的长度保持变。
从代码中很容易看到当K>=0时，处理拉伸态。当K<0时，处理收缩态。
处于收缩态时，由于K次的翻转数已用完，K已是负数，此时需要将窗口左侧增加1(i加1)，以保持窗口长度不变。其中，有行关键的代码:
K += 1- A[i]
该行代码根据A[i]的值来判断，是否需要将K进行自增操作。由于A[i]在收缩态时是需要被移出窗口的，需要判断A[i]之前是否被翻转过，如果A[i]之前是0，那么需要把翻转的次数加回去。如果A[i]之前是1，K保持不变。
分析总结：
该算法，通过动态窗口的拉伸的收缩的动作来遍历数组，可以将数组内分散的0和1纳入到窗口内，并且通过K来控制窗口的收缩，以取得一个化零为整的效果，并且在效率上非常高。