Tous les défis
Difficile 2 résolus 33.3 % de réussite

Trapping Rain Water

Compute how much rain water an elevation map holds.

Ce que vous allez apprendre

  • Calculer l'eau au-dessus de chaque barre
  • Utiliser les maxima de gauche et de droite
  • Résoudre avec deux pointeurs en O(n)

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

Exemple 1
Entrée :
heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

Sortie attendue :
expected = 6
Entré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.

Exemple 2
Entrée :
heights = [3, 2, 1]

Sortie attendue :
expected = 0
Entré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.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

# Codeur Langage Temps Mémoire Note de l'IA Solution
1 ННикита Python 885 ms - 5/5 Voir le code
2 KKosake82 Python 933 ms - 4/5 Voir le code

Apprenez des autres

Solutions de la communauté

Attention spoiler : 2 solutions complètes ci-dessous Essayez d'abord de le résoudre vous-même. Vous pouvez toujours jeter un œil au code des autres développeurs et aux avis IA. Connectez-vous et résolvez le défi pour rejoindre la discussion.