LeetCode 239. Sliding Window Maximum

파이썬 알고리즘 인터뷰 75번(리트코드 239번) Sliding Window Maximum
https://leetcode.com/problems/sliding-window-maximum/

나의 풀이(Heap 이용)

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

        while right < len(nums):
            left = right - k + 1
            if nums[right] >= nums[M]:
                M = right
                heap = []
            else:
                heapq.heappush(heap, (-nums[right], right))
                if left > M:
                    M = -1
                    while M < 0:
                        temp = heapq.heappop(heap)[1]
                        if temp >= left:
                            M = temp
            result.append(nums[M])
            right += 1

        return result

• 새로 추가되는 값이 최댓값이면 heap을 초기화,
• 그렇지 않으면 heap에 보관해둔다.
• 현재 최댓값이 윈도우를 빠져나가면 heap에서 가장 큰 값을 가져온다.

다른 풀이1(queue 이용 풀이)

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = collections.deque()
        result = []

        for i, v in enumerate(nums):
            while q and nums[q[-1]] <= v:
                q.pop()
            q.append(i)
            if q[0] <= i - k:
                q.popleft()
            if i >= k - 1:
                result.append(nums[q[0]])
        
        return result

• queue를 이용하여 위 풀이와 비슷한 논리로 푼다.
• 새로운 값 보다 작은 값은 .pop()하여 큐에서 제외시킨다.
• 새로운 값의 인덱스를 큐에 저장한다. 그러면 큐에는 새로운 값보다 큰 값들의 인덱스가 있기 때문에 큐에 저장된 인덱스의 값들은 내림차순이다. 그러니까 q[0] 의 값이 최대, q[-1]의 값이 최소다.
• 윈도우가 이동하면 최대가 윈도우 밖으로 빠져나갈 수 있다.
• q[0]가 i-k이하 인 경우 윈도우 밖으로 나간 것이므로 .popleft()해준다.
• q[0]에 해당하는 값이 현재 윈도우의 최댓값이므로 결과에 넣는다.

다른 풀이2(queue 풀이 개선)

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = collections.deque()
        result = []

        for i, v in enumerate(nums[:k]):
            while q and nums[q[-1]] <= v:
                q.pop()
            q.append(i)
        
        result.append(nums[q[0]])

        for i, v in enumerate(nums[k:], start = k):
            while q and nums[q[-1]] <= v:
                q.pop()
            q.append(i)
            if q[0] <= i - k:
                q.popleft()
            result.append(nums[q[0]])
        
        return result

• 최초 k개는 따로 한다. 최초 k개에 대한 조건문 검사 하나가 줄어서 조금 더 빠르다. n이 클 떄, 특히 k도 클 때 차이가 난다.
• 단점으로 nums[:k], nums[k:]를 하면 새로운 리스트가 생성되어 메모리 낭비가 생길 수 있다. enumerate말고 그냥 for i in range()를 사용하는 게 나을 수 있겠다.

다른 풀이3(iter 이용)

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = collections.deque()
        result = []
        it = iter(nums)

        for i, v in enumerate(itertools.islice(it, k)):
            while q and nums[q[-1]] < v:
                q.pop()
            q.append(i)
        result.append(nums[q[0]])

        for i, v in enumerate(it, start = k):
            while q and nums[q[-1]] < v:
                q.pop()
            q.append(i)
            if q[0] <= i - k:
                q.popleft()
            result.append(nums[q[0]])
        
        return result

• iter와 itertools.islice()를 이용하여 풀이2에서의 메모리 낭비를 줄임.

배운 점

• iter, islice에 대해 정리해보자.