Shulou(Shulou.com)06/01 Report--

This article is about how LeetCode finds the maximum value of a sliding window. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

Topic description

Given an array nums and the size k of the sliding window, find the maximum value in all sliding windows.

You can assume that k is always valid, and if the input array is not empty, 1 ≤ k ≤ enters the size of the array. Sample topic input: nums = [1, 3, 5, 6, 7], and k = 3.

Output: [3, 3, 5, 5, 5, 6, 7]

Explanation:

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

What should I do if the time complexity is O (N)? A relatively easy way to think of the solution is the violent method, that is, fix each starting point, then find the maximum value of the k elements after it and add it to the result in turn, so the time complexity is O (Nk). When k is very large, the efficiency is very low, how to improve the efficiency? Re-look at the title example, if we can dynamically maintain the maximum value of the current window, then when the window moves, we only need to use O (1) time to return this value to move the window to the right. If the newly added value is larger than the original maximum value, it is easy to update the maximum value directly, but here comes the problem. Moving the window to the right means that the left boundary has to move to the right. What if the left boundary just before it is the maximum? Obviously, only one variable with the maximum value is not enough, we also need to save the second largest value, the third largest value. According to the above analysis, we need to save these values in a monotonous data structure, with the maximum value in the window on one side and the minimum value on the other side. When the window moves to the right, it is divided into three parts in order: (when the window length exceeds k after adding the current value, that is, right > = k) remove the old left boundary value: if it happens to be the maximum value Also remove the corresponding value in the monotonous data structure and add a new right boundary value: at this point, you need to constantly remove the minimum value until the current new value becomes the new minimum value, because a smaller value can never be a candidate for the maximum value (old and small) (when the window length reaches k after adding the current value That is, right > = KMel 1) add the maximum value saved in the monotonous data structure to the final result. Note that 3 of the above three steps must be the last step, because you have to adjust the maximum and minimum values of the current window first, and 1 and 2 can swap positions, because you can deal with the left boundary or the right boundary first. According to the above process, we only need to deal with the insert and delete operations of the head and tail. Obviously, the double-ended queue is the most suitable data structure, and both operations only require O (1) time. The following code explains the necessary steps in detail, especially some key points in steps 1 and 2. It is convenient for everyone to understand the complexity and time complexity O (N): each value can be added to and removed from the double-ended queue at most once, for a total of 2N operations. So the time complexity is O (N) and the space complexity is O (k): the maximum number of k value codes stored in the double-ended queue is class Solution:

Def maxSlidingWindow (self, nums: List [int], k: int)-> List [int]:

# monotone double-ended queue, the minimum value of the window on the left and the maximum value of the window on the right

Q = collections.deque ()

Res = []

Left = 0

For right in range (len (nums)):

# step 1 (when the window length exceeds k after adding the current value, that is, right > = k)-remove the old left boundary value: if it happens to be the maximum, also remove the tail of the queue

# Note that if the left boundary is not the maximum, it will not exist in the queue, because there is always a larger value after it to eliminate the left boundary from the queue (operation in step 2)

If right > = k:

If nums [left] = = Q [- 1]:

Q.pop ()

Left + = 1

# step 2 (interchangeable position with step 1)-add a new right boundary value: at this point, you need to constantly remove the minimum value on the left side of the queue until the current new value becomes the new minimum value, and then insert it on the left side, because a smaller value can never be a candidate for a maximum value (old and small)

# Note that it needs to be less than and not less than or equal to, because if the minimum value is equal to the current value and is removed, and if it happens to be the maximum value, then the next time the left boundary is removed, the current value will be mistakenly removed instead of the one corresponding to the left boundary, which will lead to an error in the calculation of the maximum value later.

While q and q [0]

= kmur1)-add the maximum value on the right side of the queue to the final result

If right > = k-1:

Res.append (Q [- 1])

Return res, thank you for your reading! This is the end of the article on "how to find the maximum value of the sliding window in LeetCode". I hope the above content can be of some help to you, so that you can learn more knowledge. if you think the article is good, you can share it for more people to see!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.