Container With Most Water

Q: Qual è la complessità temporale di Container With Most Water?

La soluzione a due puntatori richiede un tempo O(n) e uno spazio extra O(1), poiché a ogni passaggio un puntatore si sposta di una posizione verso l’interno. Controllare ogni coppia richiede O(n²), mentre ordinare le linee per altezza richiede O(n log n).

Q: Perché spostare il puntatore sulla linea più corta?

L’acqua è limitata dalla linea più corta. Qualsiasi altro contenitore che mantenga quella linea ha una linea più vicina, quindi è più stretto e non più alto. Nessuno di essi può superare il contenitore che hai misurato, quindi si può scartare la linea più corta senza perdere la risposta.

Q: Container With Most Water è un problema greedy?

Sì. Ogni passaggio fa una scelta locale che non viene mai annullata: scarta la linea più corta. La scelta è sicura perché ogni contenitore che esclude non è migliore di uno già misurato, ed è per questo che il problema rientra sia tra gli algoritmi greedy sia tra quelli a due puntatori.

MedioDue puntatori Greedy

+10

Ti viene fornita una lista height di numeri interi non negativi. La linea i è una parete verticale di altezza height[i] situata nella posizione i. Qualsiasi coppia di linee forma un contenitore con il terreno, che può contenere una quantità d’acqua pari all’altezza della linea più bassa moltiplicata per la distanza tra le due linee. Le altre linee non sono d’intralcio. Restituisci la quantità massima d’acqua che una singola coppia di linee può contenere.

Funzione

maxArea(height: integer-array) → integer

heightinteger-array: le altezze delle linee alle posizioni 0, 1, 2 e così via
Restituisceinteger: la quantità massima d’acqua che possono contenere due linee

Vincoli

2 ≤ height.length ≤ 10⁴
0 ≤ height[i] ≤ 10⁴
La risposta è al massimo 10⁸, quindi rientra in un intero a 32 bit.

Esempi

Input: height = [3, 7, 2, 5, 4, 7, 3, 6]
Output: 36
Spiegazione: Le linee nelle posizioni 1 e 7, con altezze 7 e 6, sono distanti 6 e contengono 6 × 6 = 36. Le due linee più alte, i 7 nelle posizioni 1 e 5, contengono solo 7 × 4 = 28.

Per approfondire

Qui vengono ignorate le linee tra le tue due. Se ogni linea fosse una barra solida, quanta acqua si raccoglierebbe tra tutte? Riusciresti a calcolarlo anche in O(n)?

Soluzione

Controllare tutte le n²/2 coppie significa effettuare 5 × 10^7 prodotti per 10^4 linee. La quantità d'acqua dipende solo dalla linea più corta di una coppia, quindi, una volta che una linea è il lato più corto del contenitore più largo che può ancora formare, nessun contenitore più stretto che la usa può fare di meglio. Due puntatori trasformano il problema in un'unica passata da entrambe le estremità.

Controlla ogni coppia

Corretto, ma non termina sui test più grandi

Intuizione

Una coppia i < j contiene min(height[i], height[j]) × (j - i): l’acqua trabocca dal muro più corto e il fondo è largo j - i. Prova ogni coppia e conserva quella con il valore più grande.

n linee generano n(n-1)/2 coppie: circa 5 × 10^7 per 10^4 linee, e ogni volta che n raddoppia le coppie diventano quattro volte tante.

Algoritmo

Imposta best a 0.
Per ogni i e ogni j successivo, calcola min(height[i], height[j]) × (j - i).
Mantieni il maggiore tra best e quel valore.
Restituisci best.

def maxArea(height):
    n = len(height)
    best = 0
    for i in range(n):
        for j in range(i + 1, n):
            water = min(height[i], height[j]) * (j - i)
            best = max(best, water)
    return best

Prima le linee più alte

Intuizione

Se la linea i è il lato più corto di un contenitore, la sua compagna può essere qualsiasi linea almeno altrettanto alta. Quindi il contenitore migliore la abbina alla linea più lontana che sia almeno altrettanto alta.

Disponi le linee dalla più alta alla più bassa. Quando arriva il turno della linea i, ogni linea già disposta è almeno altrettanto alta, e quella più lontana è l’indice disposto più a sinistra o più a destra, lo o hi. Quindi la linea i può contenere al massimo height[i] × max(i - lo, hi - i), e il contenitore migliore viene conteggiato quando arriva il turno del suo lato più corto. Tra due linee della stessa altezza, quella disposta per seconda vede la prima come compagna.

Nel primo esempio, i 7 nelle posizioni 1 e 5 arrivano per primi e contengono 28. Il 6 in posizione 7 vede quindi lo = 1 e contiene 36. L’ordinamento richiede O(n log n) di tempo e O(n) di memoria.

Algoritmo

Ordina gli indici per altezza, dal più alto al più basso.
Imposta lo e hi sul primo indice di quell’ordine e best su 0.
Per ogni indice successivo i, calcola height[i] moltiplicato per il maggiore tra i - lo e hi - i, e conserva il valore migliore.
Aggiorna lo e hi per includere i.
Restituisci best.

def maxArea(height):
    # Indices from the tallest line to the shortest.
    order = sorted(range(len(height)), key=lambda i: height[i], reverse=True)
    lo = hi = order[0]  # leftmost and rightmost index among the lines placed so far
    best = 0
    for i in order[1:]:
        # Every placed line is at least as tall as line i, so line i is the
        # shorter side, and its best partner is the placed line farthest away.
        best = max(best, height[i] * max(i - lo, hi - i))
        lo = min(lo, i)
        hi = max(hi, i)
    return best

Due puntatori da entrambe le estremità

Intuizione

Inizia con il contenitore più largo, left = 0 e right = n-1, e supponi che height[left] ≤ height[right]. Tutti gli altri contenitori che usano la linea left la abbinano a una linea più vicina, quindi sono più stretti e non più alti di height[left]. Nessuno di loro contiene più acqua di quella che hai misurato, quindi la linea left è terminata e left si sposta di un passo verso destra. Se le altezze sono uguali, entrambe le linee sono terminate, quindi va bene spostare una qualsiasi delle due.

A ogni passo viene eliminata una linea, quindi i puntatori si incontrano dopo n-1 passi. La coppia migliore non viene mai saltata: quando viene eliminata la prima delle sue due linee, il contenitore misurato in quel momento contiene almeno altrettanta acqua.

Nel primo esempio, le posizioni 0 e 7 contengono 21 e viene eliminato il 3. Le posizioni 1 e 7 contengono 36 e viene eliminato il 6. Gli altri contengono 15, 28, 12, 10 e 2.

Algoritmo

Imposta left = 0, right = n-1 e best = 0.
Mentre left < right, calcola min(height[left], height[right]) × (right - left) e conserva il valore migliore.
Se height[left] < height[right], sposta left di un passo a destra. Altrimenti sposta right di un passo a sinistra.
Quando i puntatori si incontrano, restituisci best.

def maxArea(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        water = min(height[left], height[right]) * (right - left)
        best = max(best, water)
        # The shorter line cannot do better with any line closer in, so drop it.
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return best

Trappole e casi limite

Spostare la linea più alta. Nel primo esempio, che restituisce 21 invece di 36: il 6 in posizione 7 si allontana prima ancora di incontrare il 7 in posizione 1.
Usare la linea più alta, o la media delle due, come altezza. L'acqua trabocca dalla parete più bassa, quindi l'altezza è il minimo.
Misurare la larghezza come j - i + 1. Le linee alle posizioni i e j sono distanti j - i, quindi [4, 4] contiene 4, non 8.
Supporre che la risposta usi le linee più alte o la coppia esterna. Nel primo esempio i due 7 contengono 28 e la coppia esterna 21, mentre la risposta è 36.

Domande frequenti3

Qual è la complessità temporale di Container With Most Water?

La soluzione a due puntatori richiede un tempo O(n) e uno spazio extra O(1), poiché a ogni passaggio un puntatore si sposta di una posizione verso l’interno. Controllare ogni coppia richiede O(n²), mentre ordinare le linee per altezza richiede O(n log n).

Perché spostare il puntatore sulla linea più corta?

L’acqua è limitata dalla linea più corta. Qualsiasi altro contenitore che mantenga quella linea ha una linea più vicina, quindi è più stretto e non più alto. Nessuno di essi può superare il contenitore che hai misurato, quindi si può scartare la linea più corta senza perdere la risposta.

Container With Most Water è un problema greedy?

Sì. Ogni passaggio fa una scelta locale che non viene mai annullata: scarta la linea più corta. La scelta è sicura perché ogni contenitore che esclude non è migliore di uno già misurato, ed è per questo che il problema rientra sia tra gli algoritmi greedy sia tra quelli a due puntatori.

def maxArea(height):
    # Scrivi il codice qui

Test #1

Test #2

Argomento

height = [3, 7, 2, 5, 4, 7, 3, 6]

Output atteso

Container With Most Water

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Controlla ogni coppia

Prima le linee più alte

Due puntatori da entrambe le estremità

Trappole e casi limite

Domande frequenti3

Problemi simili