Problema
Bars of width 1 have the given heights. After rain, water collects above each bar up to the lower of the tallest bars on its left and right. Compute the total trapped water. An O(n) two-pointer solution is expected.
Implement trapped_water(heights).
Input
heights: Bar heights from left to right.
Output
Return the total units of water.
Vincoli
0 ≤ length ≤ 200,000; 0 ≤ height ≤ 100,000
Esempi
Input:
heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output atteso:
expected = 6Input:
std::vector<long long> heights = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
Output atteso:
long long expected = 6;Input:
long[] heights = new long[] {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
Output atteso:
long expected = 6;Spiegazione
Water fills the dips: 1 + 1 + 2 + 1 + 1 = 6 units.
Input:
heights = [3, 2, 1]
Output atteso:
expected = 0Input:
std::vector<long long> heights = {3, 2, 1};
Output atteso:
long long expected = 0;Input:
long[] heights = new long[] {3, 2, 1};
Output atteso:
long expected = 0;Spiegazione
Heights only go down, so water runs off: 0.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
L'acqua in ogni posizione è limitata dalla barriera più bassa tra la massima a sinistra e la massima a destra.
Suggerimento 2
Tieni traccia dei bordi da entrambe le estremità, avanzando sempre dal lato con il bordo corrente più basso.
Suggerimento 3
Fai attenzione all'input vuoto e ai plateau di altezza uguale; lì solo il lato più basso può determinare l'acqua trattenuta.
Complessità attesa
tempo O(n), spazio aggiuntivo O(1)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.