1004. Max Consecutive Ones III

Max Consecutive Ones III - LeetCode

 

주어진 이진 배열 nums에는 0과 1이 포함되어 있습니다. 여기서 최대 k번의 0을 1로 바꿀 수 있습니다. 그리고 최대한 많은 연속된 1을 만들고자 합니다.

 

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.

 

문제 요약:

이진 배열 nums가 주어지고, 최대 k번 0을 1로 뒤집을 수 있습니다.
연속된 1의 최대 길이를 찾아야 합니다.

 

풀이:

이 문제를 해결하기 위해 슬라이딩 윈도우 기법을 사용할 수 있습니다. 슬라이딩 윈도우는 연속된 서브 배열의 최대 길이를 찾는 데 유용합니다.

1. left와 right 포인터를 사용하여 윈도우를 만듭니다. 초기에 두 포인터는 모두 배열의 시작 부분을 가리킵니다.
2. right 포인터를 오른쪽으로 이동하면서 0을 만나면 k를 하나씩 줄입니다.
3. 만약 k가 음수가 되면, left 포인터를 오른쪽으로 이동하면서 0을 만날 때까지 k를 증가시킵니다.
4. 매번 right - left + 1의 길이를 업데이트하면서 연속된 1의 최대 길이를 유지합니다.
5. right 포인터를 배열의 끝까지 이동하면서 위의 과정을 반복하면 최대 길이를 찾을 수 있습니다.

class Solution {
    public int longestOnes(int[] nums, int k) {
        int leftP = 0;
        int maxLen = 0;
        int zeroCnt = 0;

        for(int rightP = 0; rightP < nums.length; rightP++){
            if(nums[rightP] == 0) zeroCnt++;
            
            if(zeroCnt > k){
                if(nums[leftP] == 0) zeroCnt--;
                leftP++;
            }
            maxLen = Math.max(maxLen, rightP - leftP + 1);
        }
        return maxLen;
    }
}