239. Sliding Window Maximum

[zeikar]

Problem link

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

Problem Summary

k 크기의 슬라이딩 윈도우에서 가장 큰 값들을 출력하는 문제.

Solution

말 그대로 슬라이딩 윈도우로 쭉 돌려가면서 큰 값이 될 후보를 덱으로 관리해주면 된다.

현재 값보다 작은 값이 이전에 나왔다면 그 값은 앞으로 최대가 될 수 없기 때문에 쭉 빼주는 연산만 해주면 된다.

Source Code

from collections import deque
from typing import List


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

        for i in range(len(nums)):
            if deq and deq[0] == i - k:
                deq.popleft()

            while deq and nums[deq[-1]] < nums[i]:
                deq.pop()

            deq.append(i)

            if i >= k - 1:
                res.append(nums[deq[0]])

        return res