How to find the maximum value of sliding window by LeetCode
Xiaobian to share with you how LeetCode to find out the maximum value of the sliding window, I believe most people still do not know how to share this article for your reference, I hope you have a lot of harvest after reading this article, let's go to understand it together!
Title Description:
Given an array of numbers and the sliding window size k, find the maximum of all sliding windows.
Examples:
Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7]
Explanation:
Maximum sliding window position
--------------- -----
[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
Thinking analysis:
Considering that the array of this problem requires that the head can be entered, deleted, and the tail can be entered and deleted, so use the double-ended queue Deque. Monotonic double-ended queue LinkedList implementation using double-ended queues.
Monotony is when we artificially specify that the elements stored are decreasing (or increasing) from the head of the queue to the tail.
That is, we maintain a monotonic bidirectional queue, each time the window slides, I take the largest value in the current window from the head of the queue, and each time a new element enters the window, I compare it to the size of the elements in the queue:
If the incoming element is larger than the last element of the queue, pop the last element of the queue and add the incoming element to the end of the queue.
If the incoming element is smaller than the tail element of the queue, add the incoming element directly to the tail of the queue.
Therefore, through this structure that can enter and exit from both the head and the tail, the maximum value of the window is maintained.
Python code # -*- coding: utf-8-*-
class Solution:
def maxInWindows(self, num, size):
# write code here
#Store subscripts that may be maximum values
maxqueue = []
#Maximum value in storage window
maxlist = []
n = len(num)
#Parameter test
if n == 0 or size == 0 or size > n:
return maxlist
for i in range(n):
#Determine whether the element corresponding to the team leader index has slipped out of the window
if len(maxqueue) > 0 and i - size >= maxqueue[0]:
maxqueue.pop(0)
while len(maxqueue) > 0 and num[i] > num[maxqueue[-1]]:
maxqueue.pop()
maxqueue.append(i)
if i >= size - 1:
maxlist.append(num[maxqueue[0]])
return maxlist
Java code: class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Deque deque=new LinkedList();
int len=nums.length;
if(len==0 ||k==0 ){
return new int[0] ;
}
int[] res=new int[len-k+1];
for(int i=0;ideque.peekLast()){
deque.removeLast(); //queue data pops up if queue element is larger than queue element
}
deque.addLast(nums[i]);//add directly to the end of the queue without loop
}
res[0]=deque.peekFirst();
for(int i=k;i
