239. Sliding Window Maximum

https://leetcode.com/problems/sliding-window-maximum/submissions/

Sliding Window Maximum - LeetCode

Solution

import heapq
from collections import defaultdict

class Solution:
    def maxSlidingWindow(self, nums, k):
        ans = [max(nums[:k])]
        pq = []
        out = defaultdict(int)

        for i in range(k):
            heapq.heappush(pq, (-nums[i], nums[i]))
        
        idx = k
        while idx < len(nums):
            heapq.heappush(pq, (-nums[idx], nums[idx]))
            out[nums[idx-k]] += 1

            while True:
                top = heapq.heappop(pq)[1]
                if out[top] == 0:
                    heapq.heappush(pq, (-top, top))
                    break
                out[top] -= 1

            ans.append(top)
            idx += 1
        return ans

• ans는 각 window에서 최대값이 들어간다.
• pq는 heapqueue로 사용될 리스트이다.
• out은 윈도우가 지나가 고려되지 않아야할 수가 저장된다.
• 첫 for문으로 pq에 window 사이즈 만큼 요소를 넣는다.
  • 최대힙을 구현하기 위해서는 (-n, n)을 넣어서 첫 요소로 정렬되도록 하고, 나중에 뒤에 있는 요소를 꺼내 쓴다.
• while문을 돌면서 window를 하나씩 옆으로 옮긴다.
  • 옮기면서 오른쪽 요소는 pq에 추가하고 왼쪽 요소는 out에 추가한다.
  • while을 한 번 더 돌면서 top이 out에 있는 지 확인한다.
  • 없으면 빠져나오고 있으면 out에 체크하고 다음 top을 다시 뽑는다.
• 그렇게 나온 top을 ans에 넣고 idx를 증가
• O(NlogN) 시간 복잡도를 가진다.

 

• while idx < len(nums): 를 하더라도 nums의 길이를 계속 계산하지 않는다. 리스트 자체에 길이 정보를 가지고 있으므로 len(nums)의 시간 복잡도는 O(1)이다.

Another 1

from collections import deque
class Solution(object):
    def add_to_dq(self, dq, nums, i):
        while len(dq) and nums[dq[-1]] <= nums[i]:
            dq.pop()
        dq.append(i)
        return

    def maxSlidingWindow(self, nums, k):
        dq = deque()
        for i in range(k):
            self.add_to_dq(dq, nums, i)

        result, start, end = [nums[dq[0]]], 1, k

        while end < len(nums):
            self.add_to_dq(dq, nums, end)
            while True:
                if dq[0] >= start:
                    result.append(nums[dq[0]])
                    break
                else:
                    dq.popleft()
            start, end = start+1,end+1
        return result

• deque를 이용한 코드로 더 빠르다.
• 가장 먼저 add_to_dq 함수를 사용하여 k크기의 윈도우에서 각 인덱스를 dq에 넣는다.
  • 이 함수는 새로 추가되는 인덱스에 해당하는 수가 이전의 수보다 크다면, 이전의 수는 사용할 일이 없으므로 다 pop 해버린다. 그래서 [8,5,2]에 과 같이 내림차순이 만들어진다.
• while문을 돌면서 윈도우를 이동시킨다.
  • idx를 넣고 dq의 left에 있는 가장 큰 수의 인덱스가 이미 지난 위치라면 pop 해버린다.
  • 아직 윈도우 내의 수라면 result에 넣고 다음 while문
• O(N) 시간 복잡도를 가진다.

Another 2

from collections import deque
class Solution(object):
    def maxSlidingWindow(self, nums, k):
        dq = deque()
        out = []
        for i, n in enumerate(nums):
            while dq and nums[dq[-1]] < n:
                dq.pop()
                
            dq += i,

            if dq[0] == i - k:
                dq.popleft()

            if i >= k - 1:
                out += nums[dq[0]],
        return out

• 위와 같이 deque를 사용했고 코드도 더 간결하고 빠르다.
• dq에 요소가 있고 dq의 마지막이 윈도우가 이동하면서 추가될 요소보다 작은 것들은 pop한다. (위와 동일하게 내림차순이 만들어진다.)
• dq += i, 를 통해서도 deque에 값을 추가할 수 있다. 콤마가 필수이다.
• dq의 처음이 윈도우에서 지나온 곳이라면 pop 한다.
• index가 k-1을 넘는 순간부터 out에 값을 추가한다.

 

• 내가 푼 방식은 heapq, defaultdict만 사용하면 되므로 lev3 정도의 풀이법
• 다른 사람들의 방식으로는 deque를 잘 사용하는 lev4 정도의 풀이법