<div id="readability-page-1" class="page"><div>
            <h2 id="%EB%AC%B8%EC%A0%9C">문제</h2><figure><a href="https://leetcode.com/problems/sliding-window-maximum/submissions/"><div><p>Loading...</p><p>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.</p><p><img src="https://leetcode.com/favicon-192x192.png"><span>LeetCode</span></p></div><p><img src="https://leetcode.com/static/images/LeetCode_Sharing.png"></p></a></figure><h2 id="%ED%92%80%EC%9D%B4">풀이</h2><h3 id="%EB%B8%8C%EB%A3%A8%ED%8A%B8-%ED%8F%AC%EC%8A%A4">브루트 포스</h3><p>당연하겠지만 TLE가 나온다.</p><pre><code>class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -&gt; List[int]:
        return [max(nums[i : i + k]) for i in range(len(nums) - k + 1)]</code></pre><h3 id="deque">Deque</h3><p>Deque를 사용해 매번 최대값을 구하지 않도록 했지만 여전히 TLE가 나온다.</p><pre><code>class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -&gt; 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</code></pre><h3 id="optimized-deque">Optimized deque</h3><p>max를 구하는 과정에서 소모되는 O(k)만큼의 연산량을 최소화한 코드.</p><pre><code>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]] &lt; nums[i]:
                    q.pop()
                else:
                    break

            q.append(i)

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

        return result</code></pre>
        </div></div>

일시불 프로그래밍

문제
풀이
브루트 포스
당연하겠지만 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

Leetcode - 239. Sliding Window Maximum

댓글