LeetCode #239 Sliding Window Maximum

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

LeetCode #239 Sliding Window Maximum

문제 풀이

슬라이딩 윈도우를 사용하는데 이 문제는 기존 최댓값이 교체될 때 이후에 들어온 값이나 남아있는 값들 중 최댓값을 최대한 빠르게 찾아야 한다. 이 문제를 해결해야 시간 복잡도를 해결할 수 있다. 문제 해결을 위해 window를 deque로 선언하고 deque의 첫 번째 값이 최대값임을 보장하도록 해보자.

• i = 0부터 len(nums) - 1까지 (시작부터 끝까지 순회)의 좌표에 대해
• 만약 i - q[0] == k라면 이번 좌표가 입력될 시 window에 있는 가장 오래된 좌표가 k의 범위를 초과하므로 popleft한다.
• q에 원소가 남아있는 동안 탐색값 nums[i]보다 nums[q[-1]]이 작다면 최댓값 결정에 쓸모가 없는 원소이므로 pop한다. 만약 탐색값보다 큰 값이 등장하면 종료한다. 이 과정으로 q에 대해 nums[q]의 값은 단조 감소 함수가 된다.
• 이후 q에 i좌표 입력한다. 만약 위 과정으로 q에 원소가 없으면 새롭게 q[0]이 된 i좌표의 값이 최댓값이고 q에 원소가 남아있다면 q[0]가 최댓값이다.
• 만약 i < k - 1이면 아직 window size보다 덜 탐색했으므로 skip, i >= k - 1이면 결과값을 저장하는 배열에 nums[q[0]]을 저장한다.
• 이후 최대값들이 저장된 배열을 리턴

python 코드

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = collections.deque()
        sol = []
        for i in range(len(nums)):
            if q and i - q[0] == k:
                q.popleft()
            while q:
                if nums[q[-1]] < nums[i]:
                    q.pop()
                else:
                    break
            q.append(i)
            if i >= k - 1:
                sol.append(nums[q[0]])
        return sol