[leetcode 1004] 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. 

 

0과 1로 구성된 배열이 있을 때 K개수 만큼 0을 1로 변경가능하다. 1로 구성된 가장 긴 배열의 길이를 찾아라.

 

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. 1 <= A.length <= 20000
2. 0 <= K <= A.length
3. A[i] is 0 or 1 

- start와 end는 인덱스. 초기값 0으로 잡는다.

- A[end]가 1이면 end를 계속 증가시킨다.

- A[end]가 0이면 남은 K를 확인한다.만약 K>0이면, K의 수를 줄이고 end를 증가시킨다.만약 K == 0이면, 더 이상 길이를 늘릴 수 없다. 길이를 구하고(end - start) 이 길이가 max인지 확인하여 업데이트 한다. 새로운 수열 길이를 계산해야 하기 때문에 start를 이동한다. 이동 위치는 start뒤에 위치한 배열 중 최초로 등장하는 0 인덱스 +1로 이동한다. 이 때부터 구간은 end와 start사이 0의 수는 K로 고정된다. 

 

#include <algorithm>

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