239. Sliding Window Maximum (Array, Queue, Sliding Window, Heap (Priority Queue), Monotonic Queue)

링크 - https://leetcode.com/problems/sliding-window-maximum/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Hard

Intuition

1) Heap

우리는 매 원소를 Heap에 넣어놓고 이 문제를 풀 수 있다. 먼저 매번 원소와 그 인덱스를 max heap에 넣는다. 그리고 heap의 최상단의 인덱스가 우리가 지워야하는 인덱스이면 계속 지워준다. 끝나면 현재의 max heap의 첫번째 원소를 ans에 집어넣는다.

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        heap = []
        for i in range(k):
            heapq.heappush(heap, [-nums[i], i])

        ans = []
        ans.append(-heap[0][0])

        for i in range(1, len(nums)-k+1):
            idx_to_push = i+k-1
            idx_to_remove = i-1
            heapq.heappush(heap, [-nums[idx_to_push], idx_to_push])
            while heap[0][1] <= idx_to_remove:
                heapq.heappop(heap)
            ans.append(-heap[0][0])

        return ans

Time Complexity: O(nlogk)입에 push하고 pop하는 과정을 n번 반복해야 하기 때문이다.

Space Complexity: O(n)우리는 heap에 최대 n개의 원소를 저장한다. 원래는 k개만 남겨야 하지만 lazy removal를 하기 때문에 이는 n까지 올라갈 수 있다.

2) Monotonic Deque

우리는 deque의 맨 앞에 가장 큰 수를 놓는 식으로 해서 이 문제를 풀 수 있다. 먼저, 매번 원소를 체크하면서 deque의 맨 오른쪽 값이 현재 수보다 작은지 확인하고, 작으면 deque를 pop한다. 그렇게 해서 가장 큰 원소가 deque의 맨 앞에 오도록 한다.

그리고 for문을 통해 나머지 원소들을 체크한다. 만약 가장 큰 원소의 인덱스가 out of range이면 제거하고 현재 가장 큰 값을 deque의 오른쪽에 넣는다.  

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        queue = deque()
        ans = []

        for i in range(k):
            while queue and nums[i] >= nums[queue[-1]]:
                queue.pop()
            queue.append(i)

        ans.append(nums[queue[0]])

        for i in range(k, len(nums)):
            if queue and queue[0] == i-k:
                queue.popleft()
            while queue and nums[i] >= nums[queue[-1]]:
                queue.pop()
            
            queue.append(i)
            ans.append(nums[queue[0]])

        return ans

Time Complexity: O(n)

Space Complexity: O(k)