[Leetcode] 2762. Continuous Subarrays

https://leetcode.com/problems/continuous-subarrays/description/

하위 배열 중에서 모든 값의 차가 2이하인 배열의 개수를 찾는 문제이다. 슬라이딩 윈도우라는 것을 배워서 도입해서 풀어봤다.

from collections import deque

class Solution:
    def continuousSubarrays(self, nums: List[int]) -> int:
        window = deque()

        nums.append(-10)
        start = 0
        window.append(nums[start])
        count = 0
        for i in range(1, len(nums)):
            next = nums[i]
            window.append(next)
            while abs(next - min(window)) > 2 or abs(next - max(window)) > 2:
                count += len(window) - 1
                window.popleft()

        return count
                

window가 움직이면서 배열을 구하는데, 이때 새로 추가된 값이 window의 최대, 최소값과 차가 2보다 클 동안 앞에서부터 날린다.
날릴 때는 해당 원소를 시작으로한느 배열의 개수를 세는데 이 길이는 현재 window 길이 - 1이 된다.
그런데 시간초과가 났다. 매번 min, max를 계산해서 그런가보다.

GPT는 저 코드를 기반으로 개선된 코드를 알려줬다.

class Solution:
    def continuousSubarrays(self, nums: List[int]) -> int:
        min_deque = deque()
        max_deque = deque()
        start = 0
        count = 0

        for i in range(len(nums)):
            while min_deque and nums[i] < nums[min_deque[-1]]:
                min_deque.pop()
            while max_deque and nums[i] > nums[max_deque[-1]]:
                max_deque.pop()
            
            min_deque.append(i)
            max_deque.append(i)
            
            while nums[max_deque[0]] - nums[min_deque[0]] > 2:
                if min_deque[0] < max_deque[0]:
                    start = min_deque.popleft() + 1
                else:
                    start = max_deque.popleft() + 1
            
            count += i - start + 1
        
        return count

최대값과 최솟값을 저장하는 deque를 만든다. 얘네는 window의 최대와 최소값을 각각 저장해주는 그런 거다. 그리고 매번 i번째 인덱스를 추가해주고, index i로 끝나는 하위 배열의 길이를 더해준다.
그러다가 만약에 min이랑 max의 차가 2보다 커지게 되면 각각의 최대, 최소값의 위치에 따라 start를 옮겨준다.

라고 코드를 이해하긴 했는데 아직 잘 모르겠따. 나중에 다시 풀어볼 문제이다.