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

Longest Subarray of 1's After Deleting One Element - LeetCode

 

주어진 이진 배열 nums에서 하나의 요소를 삭제한 후, 결과 배열에서 연속된 1로만 이루어진 가장 긴 부분 배열의 길이를 찾으며, 이 부분 배열이 없으면 0을 반환해야 합니다.

 

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.

 

문제 요약:

주어진 이진 배열 nums에서 하나의 요소를 삭제한 후, 결과 배열에서 연속된 1로만 이루어진 가장 긴 부분 배열의 길이를 찾으며, 이 부분 배열이 없으면 0을 반환해야 합니다.

풀이과정:

1. 배열 nums를 반복하면서 현재까지의 1로만 이루어진 연속된 부분 배열의 길이를 추적합니다.
2. 0을 만나면 0의 개수를 세고, 1의 연속 부분 배열 길이를 업데이트합니다.
3. 만약 0이 연속으로 나오면, 현재까지의 1로만 이루어진 부분 배열 길이를 업데이트하며 첫 번째 0 이전까지의 1은 제외합니다.
4. 최대 길이를 유지하면서 배열을 반복하고, 결과를 반환할 때 0이 없다면 최대 길이에서 1을 뺍니다.

 

class Solution {
    public int longestSubarray(int[] nums) {
        int maxLen = 0;
        int currentLen = 0;
        int zeroCnt = 0;

        for(int i = 0; i < nums.length; i++){
            int num = nums[i];

            if(num == 1) {
                currentLen++;
            }else{
                zeroCnt++;

                while(zeroCnt > 1){
                    int _num = i - 1 - currentLen;
                    if(nums[_num] == 0) {
                        zeroCnt--;
                    }else{
                        currentLen--;
                    }
                }
            }
            maxLen = Math.max(maxLen, currentLen);
        }
       return maxLen == nums.length ? maxLen -1 : maxLen;
    }
}