Description

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 Example 2:

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

Input: nums = [1,-1], k = 1 Output: [1,-1] Example 4:

Input: nums = [9,11], k = 2 Output: [11] Example 5:

Input: nums = [4,-2], k = 2 Output: [4]

Constraints:

1 <= nums.length <= 105 -104 <= nums[i] <= 104 1 <= k <= nums.length

Solution

When we move the window from left to right, when the left element i - k left the window [i - k + 1, i], we remove it from the queue. If the current element nums[i] is larger than the end of the queue x, then we can safely remove x from the queue, since the current window and any subsequence window will not take x as the maximum element. So we need to remove elements from both end of the queue and add element to the end of the queue. Therefore we need a deque.

Below is the implementation

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        queue = collections.deque()
        n = len(nums)
        ret = [0 for i in range(n - k + 1)]
        for i in range(n):
            while len(queue) and i - queue[0] + 1 > k:
                queue.popleft()
            while len(queue) and nums[queue[-1]] < nums[i]:
                queue.pop()
            queue.append(i)
            if i >= k - 1:
                ret[i - k + 1] = nums[queue[0]]
        return ret

Time complexity is O(2n), each element is added to and popped from the queue once.