Algorithm to realize the maximum value of sliding window in js

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.

Problem description

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]}.

Analysis

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:

1. {[2,3,4],2,6,2,5,1}, the maximum value at this time is 4

2. {2,[3,4,2],6,2,5,1}, the maximum value at this time is 4

3. {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

4. {2,3 ,4,[2,6,2],5,1}, the maximum value at this time is 6

5. {2,3,4,2,[6,2,5] ,1}, the maximum value at this time is 6

6. ##{2,3,4,2,6,[2,5,1]}, the maximum value at this time is 5

The idea is:

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

Code implementation

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;
}

Related recommendations:

Using two stacks to implement the queue algorithm in js

## How to use the $() function in jquery

The 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!