Home > Web Front-end > JS Tutorial > body text

Algorithm to realize the maximum value of sliding window in js

不言
Release: 2018-07-21 11:03:26
Original
3116 people have browsed it

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;
}
Copy after login

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!

Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template
About us Disclaimer Sitemap
php.cn:Public welfare online PHP training,Help PHP learners grow quickly!