239. Sliding Window Maximum (Hard)

Solution 1: Brute Force

Time Complexity: O()
Space Complexity: O()

Solution 2: Deque

from collections import deque
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        doubleEndQue = deque()
        ans = []
        
        for idx in range(len(nums)):
            # Check and remove the left window
            if doubleEndQue and doubleEndQue[0] <= idx - k:
                doubleEndQue.popleft()
                
            # Insert and compare the max elmt
            while doubleEndQue and nums[idx] > nums[doubleEndQue[-1]]:
                doubleEndQue.pop()
            doubleEndQue.append(idx)
        
            # When idx == k - 1 means 1st sliding window full, then we begin to slide K window (Like a snake)  
            if idx >= k - 1:
                ans.append(nums[doubleEndQue[0]])
        
        return ans

Time Complexity: O(N*K) // K is the size of sliding window
Space Complexity: O(K)

Solution 3: Monotonic Queue (類似 Deque)

Time Complexity: O()
Space Complexity: O()

Solution 4: DP

Time Complexity: O()
Space Complexity: O()

Reference

https://leetcode.com/problems/sliding-window-maximum/discuss/111560/Python-O(n)-solution-using-deque-with-comments
https://leetcode.com/problems/sliding-window-maximum/discuss/458121/Java-All-Solutions-(B-F-PQ-Deque-DP)-with-Explanation-and-Complexity-Analysis

Monotonic Queue
https://leetcode.com/problems/sliding-window-maximum/discuss/65885/This-is-a-typical-monotonic-queue-problem