2022/07/21 --- maximum value of sliding window;

Title Description

remaining problems ：2022/07/20— Convert a string to an integer ; Maximum sliding window
The maximum value of the queue

Their thinking

For yesterday's window maximum ： A monotonous queue , My understanding is that ------ Maintain a queue , Consider from two aspects , Take company recruitment as an example , One side , Come in, a new man , Then fire those who are weaker than the newcomers ; Another aspect , The number of the team is stable , When more than a certain number of people , Will consider firing the older . That is to say , New people have strong ability , Cut the weak , There are too many people in the team , Cut the old . According to this idea . The maximum version of the sliding window 3 The code for is as follows .

For the maximum value of the queue ： I didn't understand the topic at first . I read the comments later to understand what the topic is talking about . in general , Is to build two queues , A queue stores all the values , A queue is used to slide windows , Traverse and save the maximum value of this queue . The code will not let go .

Code implementation

The maximum version of the sliding window 3 Code for

package cz;

import java.util.ArrayDeque;
import java.util.Deque;

public class maxSlidingWindow_0721 {
    

	public static void main(String[] args) {
    
		// TODO Auto-generated method stub
		int []nums = {
    1,3,1,2,0,5};
		int k = 3;
		int [] res=maxSlidingWindow(nums,k);
		System.out.print(res[0]);

	}
	
	public static int[] maxSlidingWindow(int[] nums, int k) {
    
		
		// Determine whether it is an empty array 
		if(nums==null || nums.length==0) {
    
			return new int [0];
		}
		
		// Create a new array to save the results 
		int [] res=new int [nums.length-k+1];
		
		// Create a new double ended queue to store the array 
		Deque<Integer> queue=new ArrayDeque<>();
		
		for(int i=0,j=0;i<nums.length;i++) {
    
			// Ensure that the maximum position difference in the queue is k-1
			if(!queue.isEmpty()&& i-queue.peek()>=k) {
    
				// Remove the first element of the double ended queue 
				queue.poll();
			}
			// When the current element is larger than the end of the queue , Remove the element at the end of the queue 
			while(!queue.isEmpty()&& nums[i]>nums[queue.peekLast()]) {
    
				queue.pollLast();
			}
			// Insert the position of the current element at the end of the queue 
			queue.offer(i);
			if(i>=k-1) {
    
				// Ensure that the team leader is the maximum 
				res[j++]=nums[queue.peek()];
			}
			
			
		}
		return res;
		
		
		
	}
	

}

Experience ： Whether learning or writing , It is precisely because of the impulse of righteousness at the bottom of my heart , Will continue to achieve better themselves .