리트코드 239번 sliding window maximum (python)

Problem

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

Solution

내 풀이

from typing import List
from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        window = deque(nums[:k], maxlen=k)
        answer = [max(window)]
        for num in nums[k:]:
            window.append(num)
            answer.append(max(window))

        return answer

다른 풀이

from typing import List
from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        window = deque()
        max_v = nums[0]
        answer = []

        for idx, num in enumerate(nums):
            window.append(num)

            # set first window
            if idx < k - 1:
                if num >= max_v:
                    max_v = num
                continue

            # update max_v
            if max_v is None:
                max_v = num
                for i in range(k):
                    if nums[idx - i] > max_v:
                        max_v = nums[idx - i]

            elif num >= max_v:
                max_v = num

            answer.append(max_v)

            # pop max value, set max value
            if max_v == window.popleft():
                max_v = None

        return answer

책에 나와 있는 풀이를 참고하여 최적화를 해봤지만 시간 초과를 해결하지 못하였다.

다른 풀이 2

from typing import List
from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        result = []
        window = deque()

        for i, num in enumerate(nums):
			# step 1
            while window and window[0] < i - k + 1:
                window.popleft()
			# step 2
            while window and nums[window[-1]] < num:
                window.pop()
			# step 3
            window.append(i)
			# step 4					
            if i >= k - 1:
                result.append(nums[window[0]])

        return result

• step 1
  • 현재 index 기준으로 window의 범위를 넘어가는 값들을 모두 제거한다.
• step 2
  • window 안에 있는 새로 들어오는 숫자보다 작은 값의 index를 모두 제거한다.
  • 현재 num보다 작고 먼저 들어온 값들은 현재 num이 pop되기 전까지 max값이 될 수 없음
• step 3
  • 현재의 index window에 넣기
• step 4
  • 최대값 기록하기
  • step2 에서 들어오는 값보다 작은 모든 값을 pop하기 때문에 window[0]이 최댓값이다.

Reference

파이썬 알고리즘 인터뷰 75번