1004. Max Consecutive Ones III

https://leetcode.com/problems/max-consecutive-ones-iii/description/

문제

정답

class Solution {
    public int longestOnes(int[] nums, int k) {
        // k만큼의 0을 포함하는 슬라이딩 윈도우
        // 0을 만날때마다 count를 ++해주고, k를 넘으면, 왼쪽의 0부분을 하나 지워줌
        int count = 0;
        int answer = 0;
        int lt = 0;
        for(int rt = 0; rt < nums.length; rt++) { //rt를 nums[]의 끝까지 탐색
            if(nums[rt] == 0) { // rt가 0이라면 count++
                count++;
            }
            
            // rt가 0이어서 count가 k를 넘는다면, 
            while(count > k) { // count가 k보다 적어질 떄까지 lt를 줄여줌
                if(nums[lt] == 0) {
                    count--;
                }
                lt++;
            }
            
            answer = Math.max(answer, rt - lt + 1);
        }

        return answer;
    }
}

• 시간복잡도는 O(N)
  • rt는 0 → N-1까지 한 번 쭉 이동함 → O(N)
  • lt도 배열 전체에서 최대 N번 이동함 → O(N)
    → 둘을 더해도 O(2N) → O(N)