This article shares with you the algorithm for realizing the maximum value of the sliding window in js. The content is very good. Friends in need can refer to it. I hope it can help everyone.
Given an array and the size of the sliding window, find the maximum value of all values in the sliding window. For example, if the input array is {2,3,4,2,6,2,5,1} and the size of the sliding window is 3, then there are a total of 6 sliding windows, and their maximum values are {4,4,6, 6,6,5}; There are the following 6 sliding windows for the array {2,3,4,2,6,2,5,1}: {[2,3,4],2,6,2,5 ,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5,1}, {2,3,4 ,[2,6,2],5,1}, {2,3,4,2,[6,2,5],1}, {2,3,4,2,6,[2,5, 1]}.
Think carefully, for the array {2,3,4,2,6,2,5,1}, if the window size is 3 , then the whole process is as follows:
{[2,3,4],2,6,2,5,1}, the maximum value at this time is 4
{2,[3,4,2],6,2,5,1}, the maximum value at this time is 4
{2, 3,[4,2,6],2,5,1}, the maximum value at this time is 6, because the newly entered window 6 is larger than 4
{2,3 ,4,[2,6,2],5,1}, the maximum value at this time is 6
{2,3,4,2,[6,2,5] ,1}, the maximum value at this time is 6
Save the array subscript maxIndex of the maximum value of the current window, slide the window once, if maxIndex is still in the window, you only need to compare maxIndex Which one is greater than the value of the latest entry into the window? If the newly entered value is greater, update maxIndex, otherwise there is no need to update; if maxIndex is not within the window, all values in the current window must be traversed to find the new maxIndex
function maxInWindows(arr, size) { if(size > arr.length || size === 0) return []; var res = [], maxIndex = -1; for(var l = 0, r = size-1;r < arr.length;l++, r++){ if(maxIndex < l){ maxIndex = getMaxIndex(arr, l, r); } if(arr[r] > arr[maxIndex]){ maxIndex = r; } res.push(arr[maxIndex]); } return res; } function getMaxIndex(arr, l, r){ var index = l; for(var i = l;i <= r;i++) { if(arr[i] > arr[index]) index = i; } return index; }
Using two stacks to implement the queue algorithm in js
## How to use the $() function in jqueryThe above is the detailed content of Algorithm to realize the maximum value of sliding window in js. For more information, please follow other related articles on the PHP Chinese website!