Problem
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.
Einschränkungen
0 ≤ length ≤ 200,000; 0 ≤ height ≤ 100,000
Beispiele
Eingabe:
heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Erwartete Ausgabe:
expected = 6Eingabe:
std::vector<long long> heights = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
Erwartete Ausgabe:
long long expected = 6;Eingabe:
long[] heights = new long[] {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
Erwartete Ausgabe:
long expected = 6;Erläuterung
Water fills the dips: 1 + 1 + 2 + 1 + 1 = 6 units.
Eingabe:
heights = [3, 2, 1]
Erwartete Ausgabe:
expected = 0Eingabe:
std::vector<long long> heights = {3, 2, 1};
Erwartete Ausgabe:
long long expected = 0;Eingabe:
long[] heights = new long[] {3, 2, 1};
Erwartete Ausgabe:
long expected = 0;Erläuterung
Heights only go down, so water runs off: 0.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Die Wassermenge an jeder Position ist durch den kleineren der höchsten Balken links und rechts begrenzt.
Hinweis 2
Verfolge die Grenzen von beiden Enden und rücke immer die Seite mit der kleineren aktuellen Grenze vor.
Hinweis 3
Achte auf leere Eingaben und gleich hohe Plateaus; dort bestimmt nur die kleinere Seite das eingeschlossene Wasser.
Erwartete Komplexität
Zeit O(n), zusätzlicher Speicher O(1)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.