[알고리즘] 최대 슬라이딩 윈도우

최대 슬라이딩 윈도우

내 풀이

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        max_sliding = []
        left = 0
        right = left + k
        while right <= len(nums):
            max_sliding.append(max(nums[left: right]))
            left += 1
            right += 1
        return max_sliding

시간초과가 났다.

책 풀이

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        results = []
        window = collections.deque()
        current_max = -sys.maxsize
        for i, v in enumerate(nums):
            window.append(v)
            if i < k - 1:
                continue

            # 새로 추가된 값이 기존 최댓값보다 큰 경우 교체
            if current_max == -sys.maxsize:
                current_max = max(window)
            elif v > current_max:
                current_max = v

            results.append(current_max)

            # 최댓값이 윈도우에서 빠지면 초기화
            if current_max == window.popleft():
                current_max = -sys.maxsize

        return results

책에서 나온 풀이다. 큐를 이용해서 최적화한 것이다. 하지만 이것 역시 시간 초과가 났다.

리트코드 풀이

[알고리즘 시각화](# https://algo.monster/problems/sliding_window_maximum)

class Solution:
    # https://algo.monster/problems/sliding_window_maximum
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = deque() # 인덱스들을 저장
        res = []
        for i, cur in enumerate(nums):
            while q and nums[q[-1]] <= cur:
                q.pop()
            q.append(i)
            # 만약 윈도우 밖이면 첫 번째 element를 제거한다
            if q[0] == i - k:
                q.popleft()

            # 맨 처음 인덱스들을 넘어서 윈도우가 만들어지면, 그때부터는 매번 result에 추가한다.
            if i >= k - 1:
                res.append(nums[q[0]])

        return res

q에는 값이 아닌 인덱스가 들어간다. 큐의 가장 왼쪽에는 max 값의 인덱스가 들어가있다. 만약 새로 만난 숫자가 크다면 그보다 작은 값들을 가지고 있는 큐를 비운다. 왜냐하면 최대값만 알고싶기 때문이다. 큐의 가장 왼쪽값이 가장 큰 값이지만, 만약 그것이 윈도우 밖이라면 제거한다.
처음 알고리즘을 보고, 큐의 맨 왼쪽 값이 윈도우 밖일 때 제거한다하더라도, 그 다음 값도 윈도우 밖 값이면 어떡하나 생각했는데, 큐는 순서대로 들어온다는 것을 생각하면, 맥스값의 오른쪽은 무조건 윈도우 안에 있다.