Tutte le sfide
Difficile 1 risolta 100.0% di accettazione

Sliding Window Maximum

Report the maximum of every window of k numbers.

Cosa imparerai

  • Maintain a deque of window candidates
  • Remove values that leave the window
  • Get every window maximum in O(n)

Problema

Mostra traduzione

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.

Vincoli

1 ≤ k ≤ length ≤ 200,000

Esempi

Esempio 1
Input:
numbers = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3

Output atteso:
expected = [3, 3, 5, 5, 6, 7]
Input:
std::vector<long long> numbers = {1, 3, -1, -3, 5, 3, 6, 7};
long long k = 3;

Output atteso:
std::vector<long long> expected = {3, 3, 5, 5, 6, 7};
Input:
long[] numbers = new long[] {1, 3, -1, -3, 5, 3, 6, 7};
long k = 3;

Output atteso:
long[] expected = new long[] {3, 3, 5, 5, 6, 7};

Spiegazione

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

Esempio 2
Input:
numbers = [4, 2]
k = 1

Output atteso:
expected = [4, 2]
Input:
std::vector<long long> numbers = {4, 2};
long long k = 1;

Output atteso:
std::vector<long long> expected = {4, 2};
Input:
long[] numbers = new long[] {4, 2};
long k = 1;

Output atteso:
long[] expected = new long[] {4, 2};

Spiegazione

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

Come affrontarlo

Prova prima da solo, poi apri un suggerimento alla volta.

Suggerimento 1

The maximum can disappear when it leaves the window, so you need a structure that updates by both value and index.

Suggerimento 2

Keep candidate indices in decreasing order of their values, dropping anything outside the current window.

Suggerimento 3

Watch the first full window and windows of size one; every answer must correspond to a fully formed window.

Complessità attesa

O(n) time, O(k) extra space

Riferimenti

Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

# Programmatore Linguaggio Tempo Memoria Voto dell'IA Soluzione
1 ННикита Python 824 ms - 5/5 Vedi il codice

Impara dagli altri

Soluzioni della community

Attenzione spoiler: 1 soluzione completa sotto Prova prima a risolverla da solo. Puoi comunque sbirciare il codice degli altri sviluppatori e le recensioni AI. Accedi e risolvi la sfida per partecipare alla discussione.