LeetCode: 239. Sliding Window Maximum

가장 먼저 떠오른 방법은 Priority Queue를 사용하는 것.

Time Complexity: O(N*logN)

import heapq

class PriorityQueue:
    def __init__(self):
        self.pq = []
        self.removals = []

    def insert(self, elem):
        heapq.heappush(self.pq, -elem)

    def gettop(self):
        return -self.pq[0]

    def remove(self, elem):
        if elem == -self.pq[0]:
            heapq.heappop(self.pq)
            while self.removals and self.pq[0] == self.removals[0]:
                heapq.heappop(self.pq)
                heapq.heappop(self.removals)
        else:
            heapq.heappush(self.removals, -elem)

    def length(self):
        return len(self.pq)


class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        ret = []
        pq = PriorityQueue()
        for i in range(len(nums)):
            if pq.length() < k:
                pq.insert(nums[i])
            else:
                ret.append(pq.gettop())
                pq.remove(nums[i-k])
                pq.insert(nums[i])
        ret.append(pq.gettop())
        return ret

풀리긴 하나 느리다...

 

다른 방법이 있을까?

아래 선생님의 설명을 참고하였다.

https://leetcode.com/problems/sliding-window-maximum/discuss/871317/Clear-thinking-process-with-PICTURE-brute-force-to-mono-deque-pythonjavajavascript

Clear thinking process with PICTURE, brute force to mono deque, python/java/javascript - LeetCode Discuss

 

방법은 Monotonic Deque

Time Complexity: O(N)

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        from collections import deque
        ret = []
        q = deque()
        for i, num in enumerate(nums):
            if q and q[0] == i - k:
                q.popleft()
            
            while q and nums[q[-1]] < num:
                q.pop()
            q.append(i)

            if i >= k - 1:
                ret.append(nums[q[0]])
        
        return ret