[리트코드] max sliding window 문제

어떤 배열이 주어질때 k크기의 윈도우가 배열을 이동할때 최대 값들을 저장하여 배열로 리턴하라는 문제이다. 

leetcode.com/problems/sliding-window-maximum/

Sliding Window Maximum - LeetCode

 

1. 최적화 없이 풀기 

사실 최적화만 하지 않아도 된다면 쉬운문제이긴 하다. 

O(kn) 으로 풀면 아래와 같다. 

파이썬의 슬라이스 문법을 사용하여 슬라이딩 윈도우를 이동시키고,
그때마다 max 값을 구해서 배열에 넣으면 끝이다. 다만 이렇게 풀면 리트코드에서는 타임리미트에 걸린다. 

class Solution:
    def max_sliding_window(self, nums: List[int], k: int) -> List[int]:
        arr = []
        for i, n in enumerate(nums):
            if len(nums) >= i+k:
                arr.append(max(nums[i:i+k]))

        return arr

 

2. 데크를 사용한 최적화

데크를 사용하여 조금 더 최적화가 가능하다.

포인트는 데크에 값을 넣을때 인덱스를 넣는것이고, 매번 루프를 반복할 때마다 q[0]에 최대값의 인덱스를 두어야한다. 

코드는 아래와 같다. 

 

class Solution:
    def max_sliding_window(self, nums: List[int], k: int) -> List[int]:
        deque = []
        arr = []

        for i, n in enumerate(nums):
			
            # k개의 윈도우만 유지 되도록 한다. i가 증가될 때 deque의 0번에 있는 인덱스와 같으면 삭제한다. 
            # i - q[0] == k 가 좀 헷갈릴 수 있는데, i, q[0], k 가 각각 3, 0, 3 이라면 아래와 같은 뜻이다.
            # i가 3이면 4번째 인덱스이고 q[0]은 0번째 인덱스이니 유효한 인덱스는 1,2,3 이므로 0번을 삭제하라는 뜻이다. 
            if deque and i - deque[0] == k: 
                deque.pop(0)
			
            # nums[i]의 값보다 작은 값들은 모두 삭제한다. 
            # 이 과정을 반복함으로써 max값의 후보의 인덱스만 데크에 남게된다. 
            while deque and n > nums[deque[-1]]: 
                deque.pop()
                
            deque.append(i)
			
            # k 번째부터 결과 리스트에 최대값을 넣는다. 
            if i >= k - 1: 
                arr.append(nums[deque[0]])
        return arr

 

저렇게 하는 방식을 우선순위 큐라고 하는 것 같은데, 금방 답이 떠오르지는 않아서 다른 사람들 풀어둔 것을 참고 했다.