Sliding Window Maximum

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

주어진 nums와 범위k가 주어졌을 떄 주어진 범위 내 가장 큰 숫자들을 모아 반환하는 문제이다.

먼저 주어진 범위를 일일이 탐색하는 brute Force 방식이 있지만

nums = [1,3,-1,-3,5,3,6,7], k = 3 를 예로들면

[1,3,-1]을 탐색하고 다음으로 [3,-1,-3]을 탐색할때 3,-1은 이미 탐색하였기 떄문에 이런식으로 탐색한다면 비효율적이다.

두번쨰 방식으로 deque를 이용히는 방식이 있다.

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        res = []
        l, r = 0,0
        deq = collections.deque()

        while r< len(nums):
            while deq and nums[deq[-1]]<nums[r]:
                deq.pop()
            deq.append(r)
            if l >deq[0]:
                deq.popleft()
            if(r+1)>=k:
                res.append(nums[deq[0]])
                l+=1
            r+=1

        return res

Ex.[8,7,6,9] k=2를 예로들면

deque에 8을 우선 저장하고 이후에 7은 8보다 작기때문에 deque에 저장한다 deque=[8,7]
그리고 deque의 가장 왼쪽에 있는 8을 res에 append해준다.
그리고 다음 범위인 [7,6]을 봤을 때 범위를 지나친 8을 pop해주고 6이 7보다 작기때문에 6을 append해준다 [7,6]
그렇게 deq[0]에 범위 내 가장 큰 수를 남겨두고...
.
.
[6,9]를 보면 9는 6보다 크기때문에 6을 내보내고 9를 deque에 저장한다..

시간복잡도 o(n)