Leetcode - 239. Sliding Window Maximum

문제

Loading...

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

LeetCode

풀이

브루트 포스

당연하겠지만 TLE가 나온다.

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        return [max(nums[i : i + k]) for i in range(len(nums) - k + 1)]

Deque

Deque를 사용해 매번 최대값을 구하지 않도록 했지만 여전히 TLE가 나온다.

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        window = collections.deque(nums[:k], k)
        max_num = max(window)
        res = [0 for _ in range(len(nums) - k + 1)]
        res[0] = max_num

        for idx, num in enumerate(nums[k:]):
            if window[0] == max_num:
                window.append(num)
                max_num = max(window)
            else:
                window.append(num)
                max_num = max(max_num, num)

            res[idx + 1] = max_num

        return res

Optimized deque

max를 구하는 과정에서 소모되는 O(k)만큼의 연산량을 최소화한 코드.

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

        for i in range(len(nums)):
            # the first/left (max) element is out of the current window
            if q and i - q[0] == k:
                q.popleft()

            while q:
                # pop useles elements from last of the queue
                if nums[q[-1]] < nums[i]:
                    q.pop()
                else:
                    break

            q.append(i)

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

        return result