Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.
Example 1:
Input: nums = [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: nums = [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.
Constraints:
1 <= nums.length <= 105nums[i] is either 0 or 1.0 <= k <= nums.lengthclass Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int lt=0, rt=0, len=0;
queue<int> q; // flipped indices
while(rt<nums.size()){
while(q.size()<=k){
while(rt<nums.size() && nums[rt])
rt++;
q.push(rt++);
}
// cout << "(" << lt << ", " << rt << ")\t" << rt-1-lt << endl;
len=max(len, rt-1-lt);
lt=q.front()+1;
q.pop();
}
return min(len, (int)nums.size());
}
};