Container With Most Water

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

La soluzione con due puntatori ha una complessità temporale di O(n) e usa O(1) spazio aggiuntivo. A ogni passaggio, un puntatore si sposta di una posizione verso l'interno, quindi ci sono al massimo n-1 passaggi. Controllare ogni coppia richiede O(n²), mentre ordinare le linee in base all'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 compagna più vicina, quindi è più stretto e non più alto della linea più corta. Nessuno di essi può superare il contenitore che hai misurato, quindi puoi 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, scartando la linea più corta. La scelta è sicura perché ogni contenitore escluso dal passaggio non è migliore di uno già misurato. Ecco perché il problema rientra sia nella categoria greedy sia in quella dei due puntatori.

Q: In che cosa Container With Most Water è diverso da Trapping Rain Water?

Qui contano solo le due righe scelte e quelle comprese tra loro vengono ignorate, quindi la risposta è un singolo rettangolo. In Trapping Rain Water ogni barra è solida e l’acqua si raccoglie sopra ogni barra fino all’altezza della più bassa tra le barre più alte ai suoi due lati, quindi la risposta è una somma su tutte le posizioni. Entrambi hanno soluzioni con due puntatori in O(n), ma le regole per i puntatori e ciò che si somma sono diversi.

MedioDue puntatori Greedy

+10

Ti viene fornito un elenco height di interi non negativi. La linea i è una parete verticale di altezza height[i] situata nella posizione i. Due linee qualsiasi formano un contenitore con il terreno, che può contenere una quantità d'acqua pari all'altezza della linea più corta 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 hanno altezza 7 e 6 e distano 6, quindi contengono 6 × 6 = 36. Le due linee più alte, i 7 nelle posizioni 1 e 5, contengono solo 7 × 4 = 28, e la coppia più esterna contiene 3 × 7 = 21.

+15 test nascosti all’invio

Per approfondire

Qui le linee comprese tra le due che scegli vengono ignorate. Se ogni linea fosse invece una barra piena, quanta acqua si raccoglierebbe tra tutte? Riesci a calcolarlo anche in O(n)?

Soluzione

Ci sono circa n²/2 coppie di linee, quindi con 10^4 linee controllarle tutte significa calcolare 5 × 10^7 prodotti. La soluzione sta nel fatto che la quantità d’acqua dipende solo dalla linea più corta della coppia: una volta che sai 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 questo fatto in un’unica passata da entrambe le estremità.

Controlla ogni coppia

Corretto, ma non termina sui test più grandi

Intuizione

Ogni contenitore è una coppia di posizioni i < j. L’acqua sale finché non trabocca dalla parete più bassa, e il fondo tra le pareti è largo j - i, quindi la coppia contiene min(height[i], height[j]) × (j - i). Prova tutte le coppie, tieni quella più grande e, per definizione, avrai la risposta.

Il problema è il numero di coppie. n linee ne generano n(n-1)/2: circa 5 × 10^7 per 10^4 linee, e ogni volta che la lista raddoppia il numero quadruplica. Un linguaggio compilato riesce a elaborarle in una frazione di secondo, ma Python, Ruby o R impiegano molti secondi, e il numero cresce troppo rapidamente per qualsiasi linguaggio quando n raggiunge 10^5.

Algoritmo

Imposta best a 0.
Per ogni i e per ogni j successivo, calcola min(height[i], height[j]) × (j - i).
Conserva 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 righe più alte

Intuizione

Osserva un contenitore dal lato della sua linea più corta. Se la linea i è il lato più corto, la quantità d’acqua è height[i] moltiplicato per la distanza, e il lato opposto può essere qualsiasi linea almeno altrettanto alta. Quindi il contenitore migliore in cui i è il lato più corto abbina i alla linea più lontana che sia almeno altrettanto alta.

Per trovare rapidamente questi lati opposti, disponi le linee dalla più alta alla più bassa. Quando arriva il turno della linea i, tutte le linee disposte prima di essa sono almeno altrettanto alte, e la più lontana tra loro è all’indice disposto più a sinistra o più a destra. Tieni traccia di questi due indici, lo e hi, e la linea i può contenere al massimo height[i] × max(i - lo, hi - i). La risposta è il più grande di questi valori, perché il contenitore migliore viene conteggiato quando arriva il turno del suo lato più corto.

Nel primo esempio, i due 7 alle posizioni 1 e 5 vengono considerati per primi e contengono 28. Il 6 in posizione 7 viene considerato dopo, con lo = 1 e hi = 5, e contiene 6 × 6 = 36. Nessuna linea più corta supera questo valore. Le altezze uguali possono essere considerate in qualsiasi ordine: tra due linee della stessa altezza, quella considerata per seconda vede l’altra come lato opposto.

L’ordinamento richiede O(n log n) e la scansione O(n), quindi è abbastanza veloce. Richiede comunque O(n) di memoria per l’ordine, mentre l’approccio successivo elimina sia l’ordinamento sia la 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 mantieni 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 calcola la sua capacità. Ora si può scartare una delle due linee e la scelta è obbligata: scarta quella più bassa. Supponiamo che height[left] ≤ height[right]. Ogni altro contenitore che usa la linea left la abbina a una linea più vicina rispetto a right, quindi è più stretto, e la sua altezza è comunque al massimo height[left]. Nessuno di questi contiene più acqua di quella che hai calcolato, quindi la linea left è stata considerata e left avanza di una posizione verso destra. Spostare invece la linea più alta manterrebbe lo stesso limite per l’altezza e ridurrebbe la larghezza, quindi il risultato potrebbe solo peggiorare. Quando le due altezze sono uguali, entrambe le linee sono state considerate e va bene spostarne una qualsiasi.

A ogni passaggio si elimina definitivamente una linea, quindi dopo n-1 passaggi i puntatori si incontrano. La coppia migliore non viene mai saltata: la prima volta che si elimina una delle sue due linee, il contenitore misurato in quel momento contiene almeno altrettanta acqua.

In [3, 7, 2, 5, 4, 7, 3, 6], le posizioni 0 e 7 contengono 3 × 7 = 21. Il 3 è più basso, quindi left si sposta a 1. Le posizioni 1 e 7 contengono 6 × 6 = 36, e ora il 6 è più basso, quindi right si sposta a 6. I contenitori successivi contengono 15, 28, 12, 10 e 2, quindi la risposta resta 36.

Algoritmo

Imposta left = 0, right = n-1 e best = 0.
Finché 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 verso destra. Altrimenti sposta right di un passo verso 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

Il ciclo a due puntatori è breve, quindi gli errori stanno nei dettagli.

Spostare la linea più alta. Nel primo esempio, che restituisce 21 invece di 36: il 6 in posizione 7 è la linea più alta della prima coppia, quindi si sposta 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.
Un errore di uno nella larghezza. Le linee nelle posizioni i e j distano j - i, non j - i + 1, quindi due linee vicine contengono una quantità d’acqua pari alla loro altezza minore moltiplicata per 1.
Supporre che la risposta usi la linea più alta o la coppia più esterna. Nel primo esempio, i due 7 contengono 28 e la coppia più esterna 21, mentre la risposta è 36.
Overflow con limiti maggiori. Qui l’acqua resta sotto 10^8, ma con altezze e lunghezze vicine a 10^5 il prodotto supera 2^31 e serve un intero a 64 bit.

Domande frequenti4

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

La soluzione con due puntatori ha una complessità temporale di O(n) e usa O(1) spazio aggiuntivo. A ogni passaggio, un puntatore si sposta di una posizione verso l'interno, quindi ci sono al massimo n-1 passaggi. Controllare ogni coppia richiede O(n²), mentre ordinare le linee in base all'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 compagna più vicina, quindi è più stretto e non più alto della linea più corta. Nessuno di essi può superare il contenitore che hai misurato, quindi puoi 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, scartando la linea più corta. La scelta è sicura perché ogni contenitore escluso dal passaggio non è migliore di uno già misurato. Ecco perché il problema rientra sia nella categoria greedy sia in quella dei due puntatori.

In che cosa Container With Most Water è diverso da Trapping Rain Water?

Qui contano solo le due righe scelte e quelle comprese tra loro vengono ignorate, quindi la risposta è un singolo rettangolo. In Trapping Rain Water ogni barra è solida e l’acqua si raccoglie sopra ogni barra fino all’altezza della più bassa tra le barre più alte ai suoi due lati, quindi la risposta è una somma su tutte le posizioni. Entrambi hanno soluzioni con due puntatori in O(n), ma le regole per i puntatori e ciò che si somma sono diversi.

Python

def maxArea(height):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Input

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

Atteso

Container With Most Water

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Controlla ogni coppia

Prima le righe più alte

Due puntatori da entrambe le estremità

Trappole e casi limite

Domande frequenti4

Problemi simili