Sliding Window, max-consecutive-ones-iii 풀이

문제

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

조건

• 이진수 배열 nums 가 주어진다.
• 정수 k가 주어진다.
• nums 를 정수 k 번만큼 뒤집을 수 있다.

제약

• 1 <= nums.length <= 105
• nums[i] is either 0 or 1.
• 0 <= k <= nums.length

예시

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.

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.

풀이

내 아이디어

• subarray 힌트를 보고 sliding window 알고리즘을 떠올린다.
  • left bound, right bound, current, answer 를 사용한다.
• k 를 뒤집을 수 있는 숫자의 수로 보기보다, 포함할 수 있는 0의 개수로 보자.
• c 에 포함되어 있는 0 의 개수를 넣어두고, 이를 초과하면 l 을 줄이는 방식으로 개수를 세자.

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var longestOnes = function (nums, k) {
  let l = 0;
  let r = 0;
  let c = 0;
  let a = 0;

  for (; r < nums.length; r++) {
    if (nums[r] === 0) {
      c += 1;
    }

    while (l <= r && c > k) {
      if (nums[l] === 0) {
        c -= 1;
      }

      l += 1;
    }

    a = Math.max(a, r - l + 1);
  }

  return a;
};

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var longestOnes = function (nums, k) {
  let l = 0;
  let r = 0;
  let a = 0;

  for (; r < nums.length; r++) {
    if (nums[r] === 0) {
      k -= 1;
    }

    while (k < 0) {
      k += 1 - nums[l++];
    }

    a = Math.max(a, r - l + 1);
  }

  return a;
};

답을 보니 놓쳤던 부분

• 만일 길이 5짜리 유효한 subarray 를 찾았다면, 그 이하의 subarray 는 찾아도 아무런 의미가 없음.
  • 그보다 작은건 아무런 의미가 없음. Max consecutive ones 가 필요할 뿐임.
  • 최대 합을 구할 때와 다르게 입력이 이진수임.
    • 즉, while 문으로 left 를 반복하여 줄여나갈 필요가 없는 것임.
• 그래서 if 문을 통해서 left 를 1 씩 줄여도 무방함.
• 일단 한번 유효한 길이 n 을 찾으면 그 이후로는 n 보다 큰 길이 만 유효함

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var longestOnes = function (nums, k) {
  let l = 0;
  let r = 0;

  for (; r < nums.length; r++) {
    if (nums[r] === 0) {
      k -= 1;
    }

    if (k < 0) {
      k += 1 - nums[l++];
    }
  }

  return r - l;
};

모범 답안

class Solution {
    public int longestOnes(int[] nums, int k) {
        int left = 0, right;
        for (right = 0; right < nums.length; right++) {
            // If we included a zero in the window we reduce the value of k.
            // Since k is the maximum zeros allowed in a window.
            if (nums[right] == 0) {
                k--;
            }
            // A negative k denotes we have consumed all allowed flips and window has
            // more than allowed zeros, thus increment left pointer by 1 to keep the window size same.
            if (k < 0) {
                // If the left element to be thrown out is zero we increase k.
                k += 1 - nums[left];
                left++;
            }
        }
        return right - left;
    }
}