Hard - Sliding Window Maximum

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

Sliding Window Maximum - LeetCode

문제 설명

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Constraints:

• 1 <= nums.length <= 10 ** 5
• -10 ** 4 <= nums[i] <= 10 ** 4
• 1 <= k <= nums.length

예시

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation: 
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Input: nums = [1], k = 1
Output: [1]

풀이

from collections import deque

class Solution:
    # def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
    #     ## TLE
    #     length = len(nums)
    #     ret = [-(10 ** 4), ] * (length - k + 1)
    #     sorted_val_idx = sorted([(val, idx) for idx, val in enumerate(nums)], reverse=True)

    #     for cur_val, cur_idx in sorted_val_idx:
    #         left = max(0, cur_idx - k + 1)
    #         right = min(length - k, cur_idx)

    #         for j in range(left, right + 1):
    #             ret[j] = max(ret[j], cur_val)

    #     return ret[:length-k+1]

    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        res = []
        left, right = 0, 0
        q = deque()
        
        while right < len(nums):
            while q and nums[right] > nums[q[-1]]:
                q.pop()
            q.append(right)

            if left > q[0]:
                q.popleft()

            if right + 1 >= k:
                res.append(nums[q[0]])
                left += 1
            right += 1

        return res

 

 

첫번째 풀이는 최대값 순으로 정렬을 하고, 정렬된 최대값을 왼쪽, 오른쪽 K의 크기만큼 res에 입력한다.

무지성으로 그냥 풀다보니 k가 겹치는 부분만큼 불필요한 연산을 하게되서, 아래 Double Ended Queue를 사용한 풀이를 첨부한다.