[슬라이딩 윈도우] Leet code 239. Sliding Window Maximum

리트코드 239번
k길이의 윈도우를 처음부터 끝까지 옮겨가며 최대값들 뽑아내기

풀이1 브루트 포스

사실 문제는 매우 쉽다. 읽자마자 아래와 같은 풀이는 모두들 생각할 것입니다. 하지만... 당연히도 시간초과가 났고 이 문제의 nums의 범위가 매우 크기때문에 또한 k도 매우 커질 수 있어서 매번 max구하는 것도 부담입니다..

class Solution:
    def maxSlidingWindow(self, nums, k):
        result = []

        for i in range(1, len(nums) - k + 1):
            result.append(max(nums[i:i+3]))

풀이2

• 매번 max를 구하지 않도록 최대값을 저장하고 그 index값도 저장
• index가 window안이면 새로 추가되는 맨 끝값과 max값 비교만
• index가 window밖으로 벗어날 때만 최대값 다시 계산

class Solution:
    def maxSlidingWindow(self, nums, k):

        if len(nums) == 1:
            return nums

        max_val = nums[0]
        max_idx = 0
        result = []

        def findMax(start): # start부터 k만큼 범위안에 max값 반환 index갱신 
            max_val = nums[start]
            global max_idx
            for i in range(start, k + start):
                if nums[i] >= max_val:
                    max_idx = i
                    max_val = nums[i]

            return max_val

        # 초기값 잡기
        result.append(findMax(0))

        for i in range(1, len(nums) - k + 1):
            if max_idx < i: # max가 window벗어나면 
                if max_val > nums[i + k - 1]: # 맨끝값이 max보다 작으면 
                    max_val = findMax(i)
                else: # 맨끝값이 max보다 크면 바로 그값 
                    max_idx = i + k - 1
                    max_val = nums[i + k - 1]
            else: # max가 window안이면 
                if max_val <= nums[i + k - 1]: # 맨끝값과 비교 
                    max_idx = i + k - 1
                    max_val = nums[i + k - 1]

            result.append(max_val) 

        return result

• 매우 개선했다고 생각해서 이 풀이가 맞는줄알았다.. 하지만 또다시 시간초과 아무래도 max를 다시구하는 과정이 k값이 커졌을 때 문제인것같다.. 🥲 (역시 hard는 hard다..)
  
  
  
  

풀이3 deque + 다음 최댓값 미리 계산

리트코드에서 가장 따봉을 많이 받은 풀이이다. 자료형으로 일단 deque를 사용해서 max값을 저장해주는데 왜 굳이??? 라고 생각했다. 그런데 계속 걱정되던 한번에 max값 구하기를 하지 않고 매번 다음 최댓값을 그때그때 계산해서 저장하는 방식이었다. 저렇게 하면 확실히 줄일 수 있겠다.. 좋은 스킬이다 (저런생각 어떻게하는지 대단...👍👍)

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        from collections import deque
        q = deque() # stores *indices*
        res = []
        for i, cur in enumerate(nums):
            while q and nums[q[-1]] <= cur:
                q.pop()
            q.append(i)
            # remove first element if it's outside the window
            if q[0] == i - k:
                q.popleft()
            # if window has k elements add to results (first k-1 windows have < k elements because we start from empty window and add 1 element each iteration)
            if i >= k - 1:
                res.append(nums[q[0]])
        return res

아이디어를 정리해보자면

• 여기서 i는 윈도우의 가장 마지막 값을 가르키는 포인터이다
  (아마 매번 추가되는 것들을 점검해주기위해 뒤를 포인트로 둔것 같다)

• 새로운 값을 매번 그냥 추가해주는 것이 아니라 앞에 있었던 애들 중 자기보다 작은 값이 있으면 뒤에서부터 pop하면서 ✨자리를 찾은뒤 넣어준다✨ (다음 최대값이 미리 계산되는 꼴)

• 기존 max보다 커지면 맨앞으로 갈것이고 아니면 적당한 자리에서 자리를 잡을 것이다

• 그리고 맨 앞에값 (q[0]) 이 window안에 들어오는 것이 아니면 popleft로 버린다

• 마지막으로 i가 k-1이면 즉 윈도우가 가득 차있으면 앞에 값을 최대값으로 res에 넣어준다

• 마지막 if를 해주는 이유는 아까 i가 head가 아닌 tail을 가리키고 있기 때문에 처음에 window크기가 안됐을 때는 값을 계산해주면 안되기 때문이다.

결론 : max값이 window에서 나가도 다시 max를 계산해 줄 필요없이 바로 다음 값이 max이다