1. 문제 소개

239. Sliding Window Maximum

2. 나의 풀이

queue와 sliding window에 익숙해지기 위해서 풀어보았다.
queue를 사용해 최대값과 배열을 관리했다.
시간복잡도는 $O(n)$이다.

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        ans = []                # 각 슬라이딩 윈도우의 최댓값을 담을 결과 리스트
        q = deque()             # 윈도우 내 원소들을 "값 기준 내림차순"으로 유지하는 덱

        for i, n in enumerate(nums):     # i: 현재 인덱스, n: nums[i] 값
            # 1) 덱의 뒤에서부터 현재 값 n보다 작은 값들은
            #    앞으로도 최댓값이 될 일이 없으므로 모두 제거한다.
            #    (덱은 항상 앞에서 뒤로 갈수록 값이 감소하는 구조 유지)
            while q and q[-1] < n:
                q.pop()
            q.append(n)         # 현재 값 n을 덱의 뒤에 추가

            # 2) 윈도우가 한 칸 오른쪽으로 움직이며,
            #    윈도우 범위를 벗어난 값을 덱에서 제거해야 한다.
            #    - 윈도우의 시작 인덱스는 (i - k + 1)
            #    - nums[i - k]는 이전 윈도우의 가장 왼쪽 값.
            #    - i >= k 이고, 그 값이 덱의 맨 앞값과 같다면,
            #      더 이상 윈도우 안에 존재하지 않으므로 덱에서 제거.
            if i >= k and nums[i - k] == q[0]:
                q.popleft()

            # 3) i가 k-1 이상일 때부터, 매번 현재 윈도우의 최댓값을 기록한다.
            #    - 덱의 맨 앞값 q[0]이 항상 현재 윈도우의 최댓값.
            if i >= k-1:
                ans.append(q[0])

        return ans              # 모든 윈도우에 대한 최댓값 리스트 반환

3. 다른 풀이

없음

4. 마무리

공부는 하면 할수록 는다.