Leetcode 239. Sliding Window Maximum

문제

You are given an array of integers nums, 
there is a sliding window of size k which is moving from the very left of the array to the very right. 
You can only see the k numbers in the window.
Each time the sliding window moves right by one position.

Return the max sliding window.

정수 자료형 리스트와 슬라이딩 윈도우의 크기가 주어진다.
만들어질수 있는 모든 슬라이딩 윈도우 내부의 최댓값을 가지는 배열을 리턴하시오.

슬라이딩 윈도우

• 배열에서 검은색으로 칠해진 부분이 슬라이딩 윈도우이다.
• 5개짜리 배열에 3개 크기의 슬라이딩 윈도우는 위의 3가지가 있을수 있다.
• 윈도우가 이동하면 가장 왼쪽은 사라지고 바로 옆에 붙은 오른쪽 값이 추가된다.
• 문제에서는 각 3개의 슬라이딩 윈도우 내부의 최댓값을 가장 왼쪽에 위치하는것부터 오른쪽 순서로 담은 배열을 리턴하면 된다.

예시

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation: 
윈도우 위치                    최댓값
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

풀이

• 슬라이딩 윈도우를 잘 보면 앞의 값은 나가고, 뒤에서 추가된다는것을 알수 있다.
• 이를 잘 표현한 자료구조인 Deque ( 양방향 큐 ) 를 사용한다.

접근법

• 예시에 나온것을 보면서 생각해보자
• 첫번째 슬라이딩 윈도우 ( [1 3 -1] ) 를 만들기 위해 Deque에 추가할때, 1보다 큰 3이 슬라이딩 윈도우에 들어간 이상, 1은 최댓값이 절대 될수 없기에 본 자료구조에 있을 의미가 없다.
• 즉, 값을 넣을때 ( 슬라이딩 윈도우를 이동해 값이 추가 ) 앞에 있는 값이 더 작을 경우 그냥 빼도록 한다.
• 그렇게 되면 맨 첫 값이 최댓값이 된다.
• 근데, 슬라이딩 윈도우를 이동할때 맨 앞에 있는 값은 없애야 하는데, 이미 위 과정을 통해 없앤 값이 없어져야 할 값이면 어떻하지?
• 이를 확인하기 위해 Deque 자료형에는 값이 아닌 index를 넣는다, 왼쪽에서 제거해야하는 위치가 Deque의 맨 앞의 index와 일치할때에만 삭제한다.

코드

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
    	# 슬라이딩 윈도우의 크기가 1인 경우, 그냥 최댓값은 배열 자기 자신이나 마찬가지이다.
        if k == 1: return nums
        
        # 연산에 사용될 deque
        dq = deque()
        
        # 답이 저장될 곳
        ans = []
        
        # 첫번째 슬라이딩 윈도우를 만들고, 그 최댓값을 구해 넣는 과정
        for i in range(k):
            while dq and nums[dq[-1]] < nums[i]:
                dq.pop()
            dq.append(i)
            
        ans.append(nums[dq[0]])
        
        # 두번째 슬라이딩 윈도우부터 계산한다.
        # left : 슬라이딩 윈도우에서 사라져야할 index의 위치 ( 왼쪽 )
        for left in range(len(nums) - k):
            # deque의 첫번째 index가 left와 일치하면 사라지는 부분이기에 제거
            if left == dq[0]:
                dq.popleft()
            
            # 우측에 값을 추가하기 전에 추가되는 값보다 앞의 값이 작으면 pop 한다.
            # dq가 비어있으면 멈추도록 dq를 조건식에 넣는다.
            while dq and nums[dq[-1]] < nums[left+k]:
                dq.pop()
            
            # 오른쪽 값 추가
            dq.append(left+k)
            
            # 본 슬라이딩 윈도우의 최댓값을 append
            ans.append(nums[dq[0]])
            
        return ans