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

This article mainly introduces the relevant knowledge of "how to achieve the maximum value of sliding window in Java". The editor shows you the operation process through an actual case. The method of operation is simple and fast, and it is practical. I hope this article "how to achieve the maximum value of sliding window in Java" can help you solve the problem.

I. title

Give you an integer array nums with a sliding window of size k moving from the far left to the far right of the array. You can only see the k numbers in the sliding window. The sliding window moves only one bit to the right at a time.

Returns the maximum value in the sliding window.

Second, monotone queue analysis

Let the problem return to the maximum coverage of the window as the sliding window slides.

This question is not suitable for the priority queue, because you can know the maximum value at this time by storing k numbers in the big top heap, but the window is sliding, and the big top heap can only pop up the maximum value at a time, and other values cannot be removed. that is, the value in the sliding window cannot be maintained with the big top heap.

Therefore, queue maintenance is adopted. As the window moves, the queue is first-in, first-out.

At this time, the requirement for the queue is that the first place of the queue is the maximum, and the whole queue is decreasing.

For example: 1, 3, 3, 3, 5, 6, 7

At the beginning, the first place is the maximum value of the sliding window at this time.

Move to-3, queue: 3meme 1mai mai 3

Move to 5, queue: 5

Move to 3, queue: 5pm 3

Move to 6, queue: 6

Move to 7, queue: 7

So in order to meet the requirements, you need to customize the queue.

As can be seen from the example, there is no need for the queue to maintain all the elements in the window, just to ensure that the window is the largest at this time, and the queue elements are decreasing, as shown in the code.

Code import java.util.Deque;import java.util.LinkedList;// Custom Array class MyQueue {Deque deque = new LinkedList () / / when popping up the element, compare whether the current value to be popped is equal to the value of the queue exit, and if equal, pop / / and determine whether the queue is currently empty void poll (int val) {if (! deque.isEmpty () & & val = = deque.peek ()) {deque.poll () }} / / when adding an element, if the element to be added is larger than the element at the entrance, pop up the entry element / / ensure that the queue element is monotonously decreasing / / for example, at this time the queue element 3 is about to join the queue, which is larger than 1, so 1 pops up At this time the queue: 3Jing 2 void add (int val) {while (! deque.isEmpty () & & val > deque.getLast ()) {deque.removeLast () } deque.add (val);} / / the queue top element is always the maximum int peek () {return deque.peek ();}} class Solution {public int [] maxSlidingWindow (int [] nums, int k) {if (nums.length = = 1) {return nums;} int len = nums.length-k + 1 / / the array int [] res = new int [len]; int num = 0; / / Custom queue MyQueue myQueue = new MyQueue (); / / put the elements of the first k into the queue for (int I = 0; I < k; iBQ +) {myQueue.add (nums [I]) } res [num++] = myQueue.peek (); for (int I = k; I < nums.length; iTunes +) {/ / sliding window removes the first element to determine whether the element is placed in the queue myQueue.poll (nums [I-k]); / / the sliding window adds the last element myQueue.add (Nums [I]) / / record the corresponding maximum value res [num++] = myQueue.peek ();} return res;}} about "how to achieve the maximum value of a sliding window by Java". Thank you for reading. If you want to know more about the industry, you can follow the industry information channel. The editor will update different knowledge points for you every day.

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.