(Python3) - LeetCode (Medium) : 2593. Find Score of an Array After Marking All Elements

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

주어진 배열 nums에서, 연속적인 부분 배열(subarray) 중에서 그 배열의 최댓값과 최솟값의 차이가 2 이하인 경우를 모두 찾아내는 문제입니다.

각 원소를 한 번씩만 순회하면서 윈도우의 범위를 조절해 효율적으로 문제를 해결해야 합니다. 따라서 슬라이딩 윈도우(Sliding Window)와 모노톤 큐(Monotonic Queue)를 활용한 O(n)복잡도의 풀이를 고려합니다.

📕 풀이방법

📔 입력 및 초기화

정답 변수 answer, left, 현 index에서 최댓값 max_queue, 최솟값 min_queue 선언 후 각각 0으로 초기화합니다.

📔 풀이과정

예시 입력: nums = [2, 4, 5, 3]

1. 배열의 각 원소를 인덱스 right를 기준으로 순회하면서 다음 작업을 수행합니다:
   • min_queue: 윈도우 내에서 현재 최솟값을 유지하는 큐입니다.
   • max_queue: 윈도우 내에서 현재 최댓값을 유지하는 큐입니다.
2. 현재 원소를 기준으로 큐 갱신:
   • min_queue: nums[right]보다 큰 값이 뒤에 있다면, 더 이상 최솟값을 유지할 필요가 없으므로 뒤에서 원소를 제거(pop)합니다. 이후 right를 추가합니다.
   • max_queue: nums[right]보다 작은 값이 뒤에 있다면, 더 이상 최댓값을 유지할 필요가 없으므로 뒤에서 원소를 제거(pop)합니다. 이후 right를 추가합니다.
3. 윈도우의 범위를 조절:
   • nums[max_queue[0]] - nums[min_queue[0]] > 2인 경우, 현재 윈도우는 조건을 만족하지 않으므로 left를 증가시키며 윈도우를 축소합니다.
   • min_queue와 max_queue의 맨 앞 요소가 현재 left와 같다면, 해당 요소는 윈도우에서 제외되므로 큐의 앞에서 제거(popleft)합니다.
4. 부분 배열의 개수 계산:
   • 조정이 완료된 후, right - left + 1은 현재 윈도우에서 가능한 부분 배열의 개수를 나타냅니다. 이를 answer에 더합니다.

📔 정답 출력 | 반환

answer를 반환합니다.

---

📕 Code

📔 Python3

from collections import deque
from typing import List

class Solution:
  def continuousSubarrays(self, nums: List[int]) -> int:
    answer = 0
    left = 0
    min_queue = deque()
    max_queue = deque()

    for right in range(len(nums)):
        while min_queue and nums[min_queue[-1]] > nums[right]:
            min_queue.pop()
        min_queue.append(right)
        while max_queue and nums[max_queue[-1]] < nums[right]:
            max_queue.pop()
        max_queue.append(right)

        while nums[max_queue[0]] - nums[min_queue[0]] > 2:
            if min_queue[0] == left:
                min_queue.popleft()
            if max_queue[0] == left:
                max_queue.popleft()
            left += 1
            
        answer += right - left + 1

    return answer

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.