Algorithmus zur Realisierung des Maximalwerts des Schiebefensters in js

Dieser Artikel teilt Ihnen den Algorithmus zur Realisierung des maximalen Werts des Schiebefensters in js mit. Der Inhalt ist sehr gut. Ich hoffe, er kann allen helfen.

Problembeschreibung

Ermitteln Sie bei einem gegebenen Array und der Größe eines Schiebefensters den Maximalwert aller Werte im Schiebefenster. Wenn das Eingabearray beispielsweise {2,3,4,2,6,2,5,1} ist und die Größe des Schiebefensters 3 beträgt, gibt es insgesamt 6 Schiebefenster und deren Maximalwerte ​sind {4,4,6, 6,6,5} Es gibt die folgenden 6 Schiebefenster für das 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]}.

Analyse

Überlegen Sie sorgfältig, ob die Fenstergröße für das Array {2,3,4,2,6,2,5,1} beträgt 3 , dann ist der gesamte Prozess wie folgt:

1. {[2,3,4],2,6,2,5,1}, der Maximalwert dabei Zeit ist 4

2. {2,[3,4,2],6,2,5,1}, der Maximalwert zu diesem Zeitpunkt ist 4

3. {2, 3,[4,2,6],2,5,1}, der Maximalwert beträgt zu diesem Zeitpunkt 6, da die 6 im neuen Eingabefenster größer als 4 ist

4. {2,3 ,4,[2,6,2],5,1}, der Maximalwert beträgt zu diesem Zeitpunkt 6

5. {2 ,3,4,2,[6,2,5] ,1}, der Maximalwert beträgt zu diesem Zeitpunkt 6

6. {2,3,4,2,6,[ 2,5,1]}, der Maximalwert beträgt zu diesem Zeitpunkt 5

Die Idee ist:

Speichern Sie den Array-Index maxIndex des Maximalwerts des Stroms Fenster, schieben Sie das Fenster einmal. Wenn sich maxIndex noch im Fenster befindet, müssen Sie nur maxIndex vergleichen. Welcher Wert ist größer als der neu eingegebene Wert im Fenster? Wenn der neu eingegebene Wert größer ist, aktualisieren Sie maxIndex keine Aktualisierung erforderlich; wenn sich maxIndex nicht im Fenster befindet, müssen alle Werte des aktuellen Fensters durchlaufen werden, um die neue maxIndex zu finden

Code-Implementierung

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

Verwandte Empfehlungen:

Der Algorithmus zur Verwendung von zwei Stapeln zur Implementierung von Warteschlangen in js

So verwenden Sie die Funktion $() in jquery

Das obige ist der detaillierte Inhalt vonAlgorithmus zur Realisierung des Maximalwerts des Schiebefensters in js. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!