Problème
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.
Contraintes
0 ≤ length ≤ 200,000; 0 ≤ height ≤ 100,000
Exemples
Entrée :
heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Sortie attendue :
expected = 6Entrée :
std::vector<long long> heights = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
Sortie attendue :
long long expected = 6;Entrée :
long[] heights = new long[] {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
Sortie attendue :
long expected = 6;Explication
Water fills the dips: 1 + 1 + 2 + 1 + 1 = 6 units.
Entrée :
heights = [3, 2, 1]
Sortie attendue :
expected = 0Entrée :
std::vector<long long> heights = {3, 2, 1};
Sortie attendue :
long long expected = 0;Entrée :
long[] heights = new long[] {3, 2, 1};
Sortie attendue :
long expected = 0;Explication
Heights only go down, so water runs off: 0.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
L’eau à chaque position est limitée par la plus petite des plus hautes barres vues à gauche et à droite.
Indice 2
Suis les bornes des deux côtés, en avançant toujours du côté avec la borne courante la plus petite.
Indice 3
Fais attention à l’entrée vide et aux plateaux de même hauteur ; seul le côté le plus petit peut y déterminer l’eau retenue.
Complexité attendue
temps O(n), espace supplémentaire O(1)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.