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

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

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.