1004. Max Consecutive Ones III

方法1: sliding windowComplexity 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 <= 200000 <= K <= A.lengthA[i] is 0 or 1

方法1: sliding window

思路：

当遇到0的时候，首先判断是否还有可以flip的额度，如果还有，就flip成1，K–，right向前++。直到K = 0，此时再遇到0，需要从左边缩减被flip的0。也就是左指针前进直到跳过第一个0。每次right前进都要更新全球变量。

Complexity

Time complexity: O(n) Space complexity: O(1)

class Solution { public: int longestOnes(vector<int>& A, int K) { int left = 0, result = 0; for (int right = 0; right < A.size(); right++) { if (A[right] == 0) { if (K > 0) K--; else while (A[left++]); } result = max(result, right - left + 1); } return result; } };