Das Finden des Maximums für jedes Fenster der Größe k in einem Array

Question

Bei einem Array der Größe n und k, wie findet man das Maximum für jedes zusammenhängende Teilarray der Größe k?

Zum Beispiel

arr = 1 5 2 6 3 1 24 7
k = 3
ans = 5 6 6 6 24 24

Ich dachte daran, ein Array der Größe k zu haben und bei jedem Schritt das letzte Element zu entfernen und das neue Element hinzuzufügen und das Maximum darunter zu finden. Dies führt zu einer Laufzeit von O(nk). Gibt es eine bessere Möglichkeit, dies zu tun?

Answer 1

Sie haben davon gehört, dass dies in O(n) mit einer dequeue gemacht wird.

Nun, das ist ein bekannter Algorithmus für diese Frage, um es in O(n) zu lösen.

Die Methode, die ich erzähle, ist recht einfach und hat eine Zeitkomplexität von O(n).

Ihr Beispieleingabe:
n=10, W = 3

10 3
1 -2 5 6 0 9 8 -1 2 0

Antwort = 5 6 6 9 9 9 8 2

Konzept: Dynamisches Programmieren

Algorithmus:

1. N ist die Anzahl der Elemente in einem Array und W ist die Fenstergröße. Also, Fensternummer = N-W+1

2. Teilen Sie das Array nun in Blöcke der Größe W, beginnend ab Index 1.

   Hier in Blöcke der Größe 'W' = 3 unterteilen. Für Ihre Beispieleingabe:

   

3. Wir haben in Blöcke unterteilt, weil wir das Maximum auf 2 Arten berechnen werden A.) durch Traversieren von links nach rechts B.) durch Traversieren von rechts nach links. Aber wie??

4. Zunächst das Traversieren von links nach rechts. Für jedes Element ai im Block finden wir das Maximum bis zu diesem Element ai vom START des Blocks bis zum ENDE des Blocks. Also hier,

   

5. Zweitens das Traversieren von rechts nach links. Für jedes Element 'ai' im Block finden wir das Maximum bis zu diesem Element 'ai' vom ENDE des Blocks bis zum START des Blocks. Also hier,

   

6. Jetzt müssen wir das Maximum für jedes Teilarray oder Fenster der Größe 'W' finden. Also, beginnend vom Index = 1 bis zum Index = N-W+1.

   max_val[index] = max(RL[index], LR[index+w-1]);

   

     für index=1: max_val[1] = max(RL[1],LR[3]) = max(5,5)= 5

Ähnlich, für alle Indizes i, (i<=(n-k+1)), wird der Wert bei RL[i] und LR[i+w-1] verglichen und das Maximum dieser beiden ist die Antwort für dieses Teilarray.

Also Endgültige Antwort: 5 6 6 9 9 9 8 2

Zeitkomplexität: O(n)

Implementierungscode:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define LIM 100001 

using namespace std;

int arr[LIM]; // Eingabearray
int LR[LIM]; // Maximum von Links nach Rechts
int RL[LIM]; // Maximum von Rechts nach Links
int max_val[LIM]; // Anzahl der Teilarrays(Fenster) ist n-k+1

int main(){
    int n, w, i, k; // 'n' ist die Anzahl der Elemente im Array
                    // 'w' ist die Fenstergröße  
    cin >> n >> w;

    k = n - w + 1; // 'K' ist die Anzahl der Fenster

    for(i = 1; i <= n; i++)
        cin >> arr[i];

    for(i = 1; i <= n; i++){ // für das Maximum von Links nach Rechts
        if(i % w == 1) // das bedeutet, der BEGINN eines Blocks
            LR[i] = arr[i];
        else
            LR[i] = max(LR[i - 1], arr[i]);        
    }

    for(i = n; i >= 1; i--){ // für das Maximum von Rechts nach Links
        if(i == n) // Vielleicht ist der letzte Block nicht von Größe 'W'.
            RL[i] = arr[i]; 
        else if(i % w == 0) // das bedeutet, das ENDE eines Blocks
            RL[i] = arr[i];
        else
            RL[i] = max(RL[i+1], arr[i]);
    }

    for(i = 1; i <= k; i++)    // Maximum
        max_val[i] = max(RL[i], LR[i + w - 1]);

    for(i = 1; i <= k ; i++)
        cout << max_val[i] << " ";

    cout << endl;

    return 0;
}  

Link zum Ausführen des Codes

---

Ich werde versuchen zu beweisen: (von @johnchen902)

Wenn k % w != 1 (k ist nicht der Anfang eines Blocks)

Lassen Sie k* = Der Anfang des Blocks, der k enthält
ans[k] = max( arr[k], arr[k + 1], arr[k + 2], ..., arr[k + w - 1])
       = max( max( arr[k],  arr[k + 1],  arr[k + 2],  ..., arr[k*]), 
              max( arr[k*], arr[k* + 1], arr[k* + 2], ..., arr[k + w - 1]) )
       = max( RL[k], LR[k+w-1] )

Andernfalls (k ist der Anfang eines Blocks)

ans[k] = max( arr[k], arr[k + 1], arr[k + 2], ..., arr[k + w - 1])
       = RL[k] = LR[k+w-1]
       = max( RL[k], LR[k+w-1] )

Answer 2

Der dynamische Programmieransatz wird von Shashank Jain sehr klar erklärt. Ich möchte erklären, wie das Gleiche mit einer Warteschlange gemacht werden kann. Der Schlüssel ist, das maximale Element oben in der Warteschlange (für ein Fenster) zu halten und die nutzlosen Elemente zu verwerfen, und wir müssen auch die Elemente verwerfen, die außerhalb des Index des aktuellen Fensters liegen.
nutzlose Elemente = Wenn das aktuelle Element größer ist als das letzte Element der Warteschlange, dann ist das letzte Element der Warteschlange nutzlos.
Hinweis: Wir speichern den Index in der Warteschlange, nicht das Element selbst. Das wird aus dem Code selbst deutlicher.
1. Wenn das aktuelle Element größer ist als das letzte Element der Warteschlange, dann ist das letzte Element der Warteschlange nutzlos. Wir müssen dieses letzte Element löschen. (und weiter löschen, bis das letzte Element der Warteschlange kleiner ist als das aktuelle Element).
2. Wenn current_index - k >= q.front() bedeutet das, dass wir das Fenster verlassen, also müssen wir das Element am Anfang der Warteschlange löschen.

vector max_sub_deque(vector &A,int k)
{
    deque q;
    for(int i=0;i= A[q.back()])
            q.pop_back();
        q.push_back(i);
    }
    vector res;
    for(int i=k;i= A[q.back()] )
            q.pop_back();
        while(!q.empty() && q.front() <= i-k)
            q.pop_front();
        q.push_back(i); 
    }
    res.push_back(A[q.front()]);
    return res;
}

Da jedes Element höchstens einmal in die Warteschlange eingefügt und entfernt wird, beträgt die Zeitkomplexität O(n+n) = O(2n) = O(n).
Und die Größe der Warteschlange kann das Limit k nicht überschreiten. Also Raumkomplexität = O(k).

Answer 3

Ein O(n)-Zeitlösung ist möglich, indem man die beiden klassischen Interviewfragen kombiniert:

• Erstellen Sie eine Stapel-Datenstruktur (genannt MaxStack), die push, pop und max in O(1) Zeit unterstützt.

  Dies kann mit zwei Stapeln erreicht werden, wobei der zweite den bisher gesehenen Minimalwert enthält.

• Modellieren Sie eine Warteschlange mit einem Stapel.

  Dies kann mit zwei Stapeln erreicht werden. Das Einreihen erfolgt in einen Stapel, während das Entnehmen aus dem anderen erfolgt.

Für dieses Problem benötigen wir im Grunde eine Warteschlange, die Einreihen, Entnehmen und max in O(1) (amortisierte) Zeit unterstützt.

Die obigen zwei Punkte kombinieren, indem man eine Warteschlange mit zwei MaxStacks modelliert.

Um die Frage zu lösen, reihen wir k Elemente ein, fragen nach dem Max, nehmen heraus, reihen das k+1. Element ein, fragen nach dem Max usw. Dies liefert das Max für jedes k-große Teilarray.

Ich glaube, es gibt auch andere Lösungen.

1)

Ich glaube, die Warteschlangen-Idee kann vereinfacht werden. Wir behalten eine Warteschlange und ein Max für jedes k bei. Wir reihen ein neues Element ein und entnehmen alle Elemente, die nicht größer als das neue Element sind.

2) Halten Sie zwei neue Arrays, die das laufende Max für jeden Block von k beibehalten, ein Array für eine Richtung (links nach rechts/rechts nach links).

3) Nutzen Sie einen Hammer: Vorbearbeiten Sie in O(n) Zeit für Bereichsmaximalabfragen.

Die Lösung 1) oben könnte die optimalste sein.

Answer 4

Sie benötigen eine schnelle Datenstruktur, die Elemente hinzufügen, entfernen und eine Abfrage für das maximale Element in weniger als O(n) Zeit durchführen kann (Sie können einfach ein Array verwenden, wenn O(n) oder O(nlogn) akzeptabel ist). Sie können einen Heap, einen ausgeglichenen binären Suchbaum, eine Skip-Liste oder eine andere sortierte Datenstruktur verwenden, die diese Operationen in O(log(n)) durchführt.

Die gute Nachricht ist, dass die meisten populären Sprachen eine implementierte sortierte Datenstruktur haben, die diese Operationen für Sie unterstützt. C++ hat std::set und std::multiset (Sie benötigen wahrscheinlich letzteres) und Java hat PriorityQueue und TreeSet.

Answer 5

Hier ist die Java-Implementierung

public static Integer[] maxsInEveryWindows(int[] arr, int k) {
    Deque deque = new ArrayDeque();
    /* Verarbeitung der ersten k (oder ersten Fenster-) Elemente des Arrays */
    for (int i = 0; i < k; i++) {
        // Für jedes Element sind die vorherigen kleineren Elemente nutzlos, also
        // entferne sie aus dem deque
        while (!deque.isEmpty() && arr[i] >= arr[deque.peekLast()]) {
            deque.removeLast(); // Vom Ende entfernen
        }
        // Neues Element am Ende der Warteschlange hinzufügen
        deque.addLast(i);
    }
    List result = new ArrayList();
    // Verarbeite den Rest der Elemente, d.h. von arr[k] bis arr[n-1]
    for (int i = k; i < arr.length; i++) {
        // Das Element am Anfang der Queue ist das größte Element des
        // vorherigen Fensters, also hinzufügen zum Ergebnis.
        result.add(arr[deque.getFirst()]);
        // Entferne alle Elemente kleiner als das aktuell hinzugefügte Element
        // (entferne nutzlose Elemente)
        while (!deque.isEmpty() && arr[i] >= arr[deque.peekLast()]) {
            deque.removeLast();
        }
        // Entferne die Elemente, die sich außerhalb dieses Fensters befinden
        while (!deque.isEmpty() && deque.getFirst() <= i - k) {
            deque.removeFirst();
        }
        // Aktuelles Element am Ende des deque hinzufügen
        deque.addLast(i);
    }
    // Das maximale Element des letzten Fensters ausgeben
    result.add(arr[deque.getFirst()]);

    return result.toArray(new Integer[0]);
}

Hier ist der entsprechende Testfall

@Test
public void maxsInWindowsOfSizeKTest() {
    Integer[] result = ArrayUtils.maxsInEveryWindows(new int[]{1, 2, 3, 1, 4, 5, 2, 3, 6}, 3);
    assertThat(result, equalTo(new Integer[]{3, 3, 4, 5, 5, 5, 6}));

    result = ArrayUtils.maxsInEveryWindows(new int[]{8, 5, 10, 7, 9, 4, 15, 12, 90, 13}, 4);
    assertThat(result, equalTo(new Integer[]{10, 10, 10, 15, 15, 90, 90}));
}