Alle Herausforderungen
Schwierig 1 gelöst 100.0% Erfolgsquote

Sliding Window Maximum

Report the maximum of every window of k numbers.

Das lernst du

  • Eine Deque von Fensterkandidaten pflegen
  • Werte entfernen, die das Fenster verlassen
  • Jedes Fenstermaximum in O(n) erhalten

Problem

Slide a window of size k across the list one step at a time and report the maximum inside each window. A deque keeps this O(n).

Implement window_maximums(numbers, k).

Input

numbers: The list of integers. k: The window size.

Output

Return the maximum of each window, left to right.

Einschränkungen

1 ≤ k ≤ length ≤ 200,000

Beispiele

Beispiel 1
Eingabe:
numbers = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3

Erwartete Ausgabe:
expected = [3, 3, 5, 5, 6, 7]
Eingabe:
std::vector<long long> numbers = {1, 3, -1, -3, 5, 3, 6, 7};
long long k = 3;

Erwartete Ausgabe:
std::vector<long long> expected = {3, 3, 5, 5, 6, 7};
Eingabe:
long[] numbers = new long[] {1, 3, -1, -3, 5, 3, 6, 7};
long k = 3;

Erwartete Ausgabe:
long[] expected = new long[] {3, 3, 5, 5, 6, 7};

Erläuterung

Windows [1,3,-1], [3,-1,-3], [-1,-3,5], … have maxima 3, 3, 5, 5, 6, 7.

Beispiel 2
Eingabe:
numbers = [4, 2]
k = 1

Erwartete Ausgabe:
expected = [4, 2]
Eingabe:
std::vector<long long> numbers = {4, 2};
long long k = 1;

Erwartete Ausgabe:
std::vector<long long> expected = {4, 2};
Eingabe:
long[] numbers = new long[] {4, 2};
long k = 1;

Erwartete Ausgabe:
long[] expected = new long[] {4, 2};

Erläuterung

Windows of one element are the elements themselves: [4, 2].

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Das Maximum kann verschwinden, wenn es das Fenster verlässt, also brauchst du eine Struktur, die nach Wert und Index aktualisiert wird.

Hinweis 2

Halte Kandidatenindizes in absteigender Reihenfolge ihrer Werte und entferne alles außerhalb des aktuellen Fensters.

Hinweis 3

Achte auf das erste vollständige Fenster und auf Fenster der Größe eins; jede Antwort muss zu einem vollständig gebildeten Fenster gehören.

Erwartete Komplexität

Zeit O(n), zusätzlicher Speicher O(k)

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

# Coder Sprache Zeit Speicher KI-Bewertung Lösung
1 ННикита Python 824 ms - 5/5 Code ansehen

Von anderen lernen

Community-Lösungen

Achtung Spoiler: 1 vollständige Lösung unten Versuche es zuerst selbst zu lösen. Du kannst trotzdem einen Blick auf den Code und die KI-Reviews anderer Entwickler werfen. Melde dich an und löse die Aufgabe, um an der Diskussion teilzunehmen.