239.Sliding_Window_Maximum(Hard).md

239. Sliding Maximum Window (Hard)

Date and Time: Jul 12, 2024, 17:46 (EST)

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

Question:

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.

Example 1:

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

Constraints:

• 1 <= nums.length <= 10^5

• -10^4 <= nums[i] <= 10^4

• 1 <= k <= nums.length

KeyPoints:

This question uses monotonic decreasing queue to solve. The deque can make sure the queue is always keeping the max of a window and is always decreasing (because new max will replace all elements < new max).

deque is used to record the index of nums, because we need to use it to update l, when l > deque[0], it means the deque has moved and we should update l.

So in the while loop for r, we repeatly check if new element > deque's last element, so we can make sure we always keep max. After the first inner while loop, we check if l > deque's first index to check if the first index in deque is outdated and should be removed. Lastly, if r + 1 is outside of the first window, we can start appending the first element in deque (max in window), and move window by 1.

Naive Solution:

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # Inefficient, O(k * (n-k))
        l, r = 0, 0
        res = []
        while l <= len(nums) - k:
            r = l + k - 1
            tmp = nums[l]
            for i in range(l, r + 1):
                tmp = max(tmp, nums[i])
            res.append(tmp)
            l += 1
        return res

Time Complexity: $O(k * (n - k))$
Space Complexity: $O(n)$

My Solution:

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        deque = collections.deque()
        l, res = 0, []
        for r in range(len(nums)):
            # Check if new element is greater than deque's last element
            # In that case we can make sure we always keep max in deque
            while deque and nums[r] >= nums[deque[-1]]:
                deque.pop()
            deque.append(r)
            # If l > deque's first index, remove it in deque
            if l > deque[0]:
                deque.popleft()
            # If r + 1 is outside of the first window, we can start
            # appending the first element in deque (max in window) to res,
            # and move window by 1
            if r + 1 >= k:
                res.append(nums[deque[0]])  # element not index
                l += 1
        return res

Time Complexity: $O(n)$
Space Complexity: $O(n)$