Leetcode: 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.

 

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation: 
Window position                Max
---------------               -----
[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

 

 

크기 k의 sliding window 내에서의 Max값을 구하는 문제이다. Brute force로 매번 max를 계산하면 O(NK)의 시간이 소요된다. 

이 때, Monotone Queue (Monotone Deque) 라는 테크닉을 쓰면, Time Complexity를 O(N)으로 줄일 수 있다. (Segment Tree를 사용하면 O(KlogN)으로 풀 수도 있으나, 이 풀이에서는 monotone queue에 대해 설명한다.)

Monotone Queue는 Queue를 사용하되, 그 내의 element가 단조증가/단조감소로 유지되는 Queue이다. stack -> queue를 사용한다는 것을 제외하면 Monotone Stack과 완전히 동일하다. Monotone Stack을 사용한 문제는 jyeonth.tistory.com/11?category=98254 가 있다. 

풀이는 아래와 같다. 

class Solution:
    def maxSlidingWindow(self, nums, k):
        queue, ans = deque(), []  # queue: list of index where nums[index] is decreasing
        for i, n in enumerate(nums):
            while queue and nums[queue[-1]] < n: 
            	queue.pop()
            queue.append(i)
            if queue[0] == i - k: 
            	queue.popleft()
            if i >= k - 1: 
            	ans.append(nums[queue[0]])

        return ans

 

우리가 궁금한 것은 구간의 max일 뿐이며, 해당 max가 sliding window를 벗어나는 경우를 고려하여 next max를 알 수만 있으면 된다. 이를 위해, nums를 차례대로 순회하며 queue는 nums의 index를 저장하고, nums[0] -> nums[last_index]가 단조 감소할 수 있도록 index를 유지한다. nums[i]를 보는 시점은 (nums[i-k+1], nums[i-k+1], nums[i-k+2], .... , nums[i]) 의 sliding window를 보는 시점과 같다. (단, i >= k-1 일 때)

 

nums[i]를 볼 때에 queue의 rightmost element보다 이 값이 더 크다면, queue에서 해당 값을 rightpop()한다. 이는 monotone stack을 유지하는 방법과 동일하다. queue는 단조감소하기 때문에, 특정 구간에서의 max값은 queue의 leftmost element (queue[0])이다. 

 

다만, sliding window가 움직이기 때문에, queue[0]이 window의 범위를 벗어났다면 해당 값을 사용할 수 없으므로 leftpop()한다. 양옆에서 element를 뽑아야 하기 때문에, 단순 queue는 아니고 deque을 사용해야한다.

 

그러므로 nums[i]까지 살펴봤을 때에 queue에 없는 원소는 sliding window 범위를 벗어났거나, window 범위 내에 있지만 nums[i]보다 작은 값들이므로, 고려할 필요가 없다. 

 

 

링크: leetcode.com/problems/sliding-window-maximum/

Sliding Window Maximum - LeetCode