Schwierig 2 gelöst 33.3% Erfolgsquote

Trapping Rain Water

Compute how much rain water an elevation map holds.

Das lernst du

  • Das Wasser über jedem Balken berechnen
  • Linke und rechte Maxima verwenden
  • Es mit zwei Zeigern in O(n) lösen

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

Beispiel 1
Eingabe:
heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

Erwartete Ausgabe:
expected = 6
Eingabe:
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.

Beispiel 2
Eingabe:
heights = [3, 2, 1]

Erwartete Ausgabe:
expected = 0
Eingabe:
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.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

# Coder Sprache Zeit Speicher KI-Bewertung Lösung
1 ННикита Python 885 ms - 5/5 Code ansehen
2 KKosake82 Python 933 ms - 4/5 Code ansehen

Von anderen lernen

Community-Lösungen

Achtung Spoiler: 2 vollständige Lösungen unten Versuche es zuerst selbst zu lösen. Du kannst trotzdem einen Blick auf den Code und die KI-Reviews anderer Entwickler werfen. Melde dich an und löse die Aufgabe, um an der Diskussion teilzunehmen.