Topic describes

Given an array nums and the size k of the sliding window, find the maximum number of sliding Windows.

Example: the input: nums = [1, 3, 1, 3,5,3,6,7], and k = 3 output:,3,5,5,6,7 [3]

The maximum position of the sliding window --------------- ----- [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
Copy the code

A monotonous queue

  1. Array traversal is divided into two stages: before and after window formation
  2. Before the window is formed, we only record the largest element of all the previously traversed elements in the queue at a time, and add this maximum element to the RES
  3. After the window is formed, we need to adjust the element in the queue to the largest element each time we traverse an element
    1. During window sliding, the header element (the largest element) may slide out of the window, so we first determine whether the header element is equal to the current sliding element, and if so, remove the header element from the window
    2. For new elements that enter the window, we compare the new elements to those in the queue. Discard all outcasts smaller than the new element and add the new element to the team
    3. We add the header element to the RES each time we traverse

Sample code:

def maxSlidingWindow(self, nums: List[int], k: int) - >List[int] :
    if not nums or k == 0:
        return []
    res, deque = [], []

    # before forming the first window
    for i in range(k):
        while deque and deque[-1] < nums[i]:
            deque.pop()
        deque.append(nums[i])
    res = [deque[0]]

    After the first window is formed
    for i in range(k, len(nums)):
        if deque[0] == nums[i - k]: # will slide out the maximum window queue
            deque.pop(0)
        while deque and deque[-1] < nums[i]:
            deque.pop()
        deque.append(nums[i])
        res.append(deque[0])

    return res
Copy the code