[Leetcode] 1493. Longest Subarray of 1's After Deleting One Element

문제

Given a binary array nums, you should delete one element from it.
Return the size of the longest non-empty subarray containing only 1's in the resulting array. Return 0 if there is no such subarray.
 
Example 1:
Input: nums = [1,1,0,1] Output: 3 Explanation: After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1's.
Example 2:
Input: nums = [0,1,1,1,0,1,1,0,1] Output: 5 Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].
Example 3:
Input: nums = [1,1,1] Output: 2 Explanation: You must delete one element.
 
Constraints:
1 <= nums.length <= 105nums[i] is either 0 or 1

 

풀이1

처음 풀이는 냅다 1의 갯수를 세고 연속적으로 가장 큰 두개의 수의 합을 찾았다.

뭔가 이 문제가 의도한 dynamic programming 이나 sliding window를 쓰진 않았지만 가장 direct한 풀이지 않나 싶다.

 

풀이2

 

그 다음은 이 문제에서 의도한 dynamic programming 이나 sliding window중, sliding window를 사용해 풀었다.

쭉 오른쪽으로 가면서 1의 갯수를 세다가 0이 2번 나오는 시점부터 왼쪽 window를 줄여나갔다.

 

코드1

int longestSubarray(int* nums, int numsSize) {
    if(numsSize == 1 && nums[0]==0) return 0;

    int len[numsSize];
    int index=0;
    int n = 0;
    memset(len, 0, sizeof(len));
    
    for(int i=0; i<numsSize; i++) {
        if(nums[i]) n++;
        else {
            len[index++] = n;
            n=0;
        }
    }
    if(n) len[index++] = n;

    if(index==1) return len[index-1]-1;

    int max = len[0];
    for(int i=1; i<index; i++) {
        max = (len[i]+len[i-1] > max) ? len[i]+len[i-1] : max;
    }
    return max;

}

 

코드2(sliding window)

 

int longestSubarray(int* nums, int numsSize) {
    // sliding window approach
    int zero = 0, max = 0, j = 0;
    for(int i=0; i<numsSize; i++) {
        if(nums[i] == 0) zero++;
        while(zero > 1) { // shrink from left when zero=2
            if(nums[j] == 0) zero--;
            j++;
        }
        if(max < i-j) max = i-j;
    }
    return max;
}