Algorithme pour réaliser la valeur maximale de la fenêtre coulissante en js

Cet article partage avec vous l'algorithme pour réaliser la valeur maximale de la fenêtre coulissante en js. Le contenu est très bon. Les amis dans le besoin peuvent s'y référer. J'espère que cela pourra aider tout le monde.

Description du problème

Étant donné un tableau et la taille d'une fenêtre glissante, trouvez la valeur maximale de toutes les valeurs dans la fenêtre glissante. Par exemple, si le tableau d'entrée est {2,3,4,2,6,2,5,1} et que la taille de la fenêtre glissante est 3, alors il y a un total de 6 fenêtres glissantes et leurs valeurs maximales ​sont {4,4,6, 6,6,5} ; Il existe les 6 fenêtres glissantes suivantes pour le tableau {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]}.

Analyse

Réfléchissez bien, pour le tableau {2,3,4,2,6,2,5,1}, si la taille de la fenêtre est 3 , alors l'ensemble du processus est le suivant :

1. {[2,3,4],2,6,2,5,1}, la valeur maximale à ce le temps est 4

2. {2,[3,4,2],6,2,5,1}, la valeur maximale à ce moment est 4

3. {2, 3,[4,2,6],2,5,1}, la valeur maximale à ce moment est 6, car le 6 dans la nouvelle fenêtre de saisie est supérieur à 4

4. {2,3 ,4,[2,6,2],5,1}, la valeur maximale à ce moment est 6

5. {2 ,3,4,2,[6,2,5] ,1}, la valeur maximale à ce moment est 6

6. {2,3,4,2,6,[ 2,5,1]}, la valeur maximale à ce moment est 5

L'idée est :

Enregistrer l'indice du tableau maxIndex de la valeur maximale du courant fenêtre, faites glisser la fenêtre une fois, si maxIndex est toujours dans la fenêtre, il vous suffit de comparer maxIndex Laquelle est supérieure à la valeur de la dernière entrée dans la fenêtre Si la valeur nouvellement saisie est supérieure, mettez à jour maxIndex, sinon il y a ? pas besoin de mettre à jour ; si maxIndex n'est pas dans la fenêtre, il faut parcourir toutes les valeurs de la fenêtre courante pour trouver le nouveau maxIndex

Implémentation du code

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

Recommandations associées :

L'algorithme d'utilisation de deux piles pour implémenter des files d'attente en js

Comment utiliser la fonction $() en jquery

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!