리트코드 - 1493. Longest Subarray of 1's After Deleting One Element

https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/description/

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

이진 배열의 숫자가 주어지면 이 배열에서 하나의 요소를 삭제해야 한다.
결과 배열에서 1만 포함하는 비어 있지 않은 가장 긴 하위 배열의 크기를 반환한다. 그러한 하위 배열이 없으면 0을 반환한다.

 

접근 방식

1. 슬라이딩 윈도우를 사용하여 현재 윈도우에 있는 1의 수를 추적한다.
2. 0이 발견되었을 때 아직 0을 제거하지 않았다면 0을 건너뛰고 창을 계속 확장한다.
3. 이미 0을 건너뛰고 다른 0을 발견하면 창의 왼쪽 포인터를 현재 창에서 첫 번째 0의 오른쪽으로 이동한다.
4. 이 과정에서 발견되는 최대 창 크기를 추적한다.
5. 1의 하위 배열을 최대화하기 위해 하나의 요소를 삭제할 수 있으므로 최종 답은 찾은 최대 창 크기보다 하나 작아진다(창 크기에 건너뛴 0이 포함되므로).

 

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        left, zero_count, res = 0, 0, 0

        for right in range(len(nums)): # O(n)
            if nums[right] == 0: # O(1)
                zero_count += 1 # O(1)
            
            while zero_count > 1: # O(m)
                if nums[left] == 0: # O(1)
                    zero_count -= 1 # O(1)
                left += 1 # O(1)
            
            res = max(res, right - left + 1 - zero_count) # O(1)
        
        return res - 1 if res == len(nums) else res # O(1)

 

복잡도

시간 복잡도 : 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이다. while zero_count > 1: 연산의 경우 최악의 경우 O(n)의 시간복잡도를 가질 수 있으나, 배열의 순회 안에서 진행되므로 n^2이 되지는 않는다.

 

공간 복잡도 : 별도의 자료 구조를 생성하지 않으므로 공간 복잡도는 O(1)이다.