Trapping Rain Water
Une rangée de barres se tient côte à côte, chacune ayant une largeur d’une unité : height[i] correspond à la hauteur de la barre i. La pluie tombe sur la rangée et s’accumule dans les creux entre les barres. L’eau reste au-dessus d’une barre uniquement si une barre plus haute se trouve quelque part à sa gauche et quelque part à sa droite ; au-delà de la première et de la dernière barre, elle s’écoule.
Renvoie le nombre total de carrés unitaires d’eau que la rangée retient.
Fonction
- heightinteger-array
- la hauteur de chaque barre, de gauche à droite
- Renvoieinteger
- le nombre total d’unités d’eau piégées
Contraintes
1 ≤ height.length ≤ 2 × 1040 ≤ height[i] ≤ 105- Chaque barre mesure une unité de largeur, et l’eau ne reste pas au-delà de la première ni de la dernière barre.
Exemples
- Entrée
- height = [0, 3, 1, 0, 2, 5, 1, 2]
- Sortie
- 7
- Explication
- Entre le 3 et le 5, l’eau monte jusqu’au niveau 3 : elle contient 2 unités au-dessus de la barre de 1, 3 au-dessus de celle de 0 et 1 au-dessus de celle de 2. Le 1 près de la fin se trouve entre le 5 et un 2, son niveau est donc 2 et il contient 1 unité. 2 + 3 + 1 + 1 = 7.
- Entrée
- height = [4, 1, 3, 0, 5]
- Sortie
- 8
- Explication
- Le mur le plus bas est le 4 à gauche, donc toute la dépression se remplit jusqu’au niveau 4 : 3 unités au-dessus du 1, 1 au-dessus du 3 et 4 au-dessus du 0, ce qui fait 8. Le 5 à droite ne fait pas monter le niveau, car l’eau déborderait d’abord par-dessus le 4.
- Entrée
- height = [1, 2, 4, 2, 1]
- Sortie
- 0
- Explication
- Les barres montent jusqu’à 4, puis redescendent. Chaque barre a un côté au-delà duquel rien n’est plus haut, donc l’eau s’écoule et la réponse est 0.
+17 tests cachés à la soumission
Pour aller plus loin
Supposons que les barres forment une grille 2D de hauteurs et que l’eau puisse s’échapper dans les quatre directions. Comment compteriez-vous alors l’eau piégée ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Oublie toute la rangée et regarde une seule barre. Jusqu’à quelle hauteur l’eau peut-elle monter au-dessus de la barre
i, et quelles barres déterminent cette hauteur ?Le niveau d’eau au-dessus de la barre
iest le plus petit de deux nombres : la barre la plus haute depuis le début jusqu’ài, et la barre la plus haute depuisijusqu’à la fin. La barreiretient ce niveau moins sa propre hauteur. Les deux maximums cumulés peuvent être calculés en un seul parcours depuis chaque extrémité.Tu n’as besoin que du plus petit des deux maxima. Place un pointeur à chaque extrémité et garde en mémoire la barre la plus haute que chaque pointeur a dépassée. Le niveau du pointeur situé sur la barre la plus basse est déterminé par son propre maximum courant : ajoute cette quantité d’eau, puis déplace ce pointeur vers l’intérieur. Arrête-toi lorsque les pointeurs se rejoignent.
Solution
L’eau au-dessus de chaque barre dépend de barres qui peuvent être éloignées des deux côtés ; se limiter aux voisines donne donc un résultat erroné. La solution tient en une formule : le niveau au-dessus d’une barre est le plus petit de la barre la plus haute à sa gauche et de la barre la plus haute à sa droite. Rechercher ces deux maximums depuis chaque barre est lent ; les stocker dans deux tableaux rend l’algorithme linéaire, et deux pointeurs qui avancent toujours du côté le plus bas ne nécessitent aucun tableau.
Parcourez les deux côtés à partir de chaque barre
Correcte, mais ne termine pas sur les plus gros tests
Intuition
Comptez l’eau colonne par colonne. L’eau au-dessus de la barre i monte jusqu’à déborder par le côté le plus bas de ses deux murs. Le mur gauche est la barre la plus haute entre l’indice 0 et i ; le mur droit est la barre la plus haute entre i et la fin. Le niveau est donc min(leftMax, rightMax), et la quantité d’eau au-dessus de la barre i est ce niveau moins height[i].
Prenez [0, 3, 1, 0, 2, 5, 1, 2] et la barre de hauteur 0 à l’indice 3. La barre la plus haute à sa gauche mesure 3, et celle à sa droite, 5. Le niveau est 3, donc 3 unités d’eau s’y accumulent. Pour celle de hauteur 1 à l’indice 6, les murs mesurent 5 et 2 : le niveau est 2 et elle retient 1 unité d’eau.
Les deux parcours incluent la barre i elle-même. Cela évite que le résultat soit négatif : lorsque la barre i est plus haute que tout ce qui se trouve d’un côté, la hauteur maximale de ce côté est sa propre hauteur, le niveau lui est égal, et elle retient 0 unité d’eau. C’est aussi pourquoi les première et dernière barres retiennent toujours 0 unité d’eau.
Le problème, c’est le coût. Chaque barre parcourt toute la rangée, une moitié vers la gauche et l’autre vers la droite, soit un total de n × n lectures : 4 × 10^8 pour 2 × 10^4 barres. Les parcours répètent aussi les mêmes opérations : la barre la plus haute à gauche de l’indice 5 est la barre la plus haute à gauche de l’indice 4, avec une comparaison de plus, tandis que la force brute recalcule tout depuis zéro.
Algorithme
- Définir
watersur 0. - Pour chaque indice
i, parcourir les indices de 0 àipour trouverleftMax. - Parcourir les indices de
ijusqu'au dernier indice pour trouverrightMax. - Ajouter
min(leftMax, rightMax) - height[i]àwater. - Renvoyer
water.
def trap(height):
n = len(height)
water = 0
for i in range(n):
# The tallest bar at or left of i, and the tallest at or right of i.
left_max = 0
for j in range(i + 1):
left_max = max(left_max, height[j])
right_max = 0
for j in range(i, n):
right_max = max(right_max, height[j])
water += min(left_max, right_max) - height[i]
return waterPré-calculer la barre la plus haute de chaque côté
Intuition
La formule reste la même ; seule la façon d’obtenir les deux murs change. La barre la plus haute de 0 à i est la plus grande entre la barre la plus haute de 0 à i-1 et height[i]. Ainsi, un passage de gauche à droite remplit un tableau leftMax, chaque élément étant construit à partir du précédent. Un passage de droite à gauche remplit rightMax de la même façon. Un troisième passage additionne min(leftMax[i], rightMax[i]) - height[i] pour chaque barre.
Pour [0, 3, 1, 0, 2, 5, 1, 2] : leftMax = [0, 3, 3, 3, 3, 5, 5, 5] et rightMax = [5, 5, 5, 5, 5, 5, 2, 2]. Les plus petites de leurs valeurs donnent les niveaux [0, 3, 3, 3, 3, 5, 2, 2]. Soustrais les hauteurs et tu obtiens [0, 0, 2, 3, 1, 0, 1, 0], dont la somme est 7.
Chaque passage parcourt chaque barre une fois, donc le temps d’exécution est O(n) : environ 6 × 10^4 étapes pour 2 × 10^4 barres au lieu de 4 × 10^8. Le prix à payer est deux tableaux supplémentaires de n nombres. C’est la version à privilégier d’abord en entretien : il est difficile de se tromper, et l’approche suivante permet de supprimer les tableaux, sans changer d’idée.
Algorithme
- Remplis
leftMaxde gauche à droite :leftMax[0] = height[0], puisleftMax[i] = max(leftMax[i-1], height[i]). - Remplis
rightMaxde droite à gauche :rightMax[n-1] = height[n-1], puisrightMax[i] = max(rightMax[i+1], height[i]). - Pour chaque indice, ajoute
min(leftMax[i], rightMax[i]) - height[i]au total. - Retourne le total.
def trap(height):
n = len(height)
left_max = [0] * n # tallest bar from index 0 to i
right_max = [0] * n # tallest bar from index i to n-1
left_max[0] = height[0]
for i in range(1, n):
left_max[i] = max(left_max[i - 1], height[i])
right_max[n - 1] = height[n - 1]
for i in range(n - 2, -1, -1):
right_max[i] = max(right_max[i + 1], height[i])
water = 0
for i in range(n):
water += min(left_max[i], right_max[i]) - height[i]
return waterDeux pointeurs qui déplacent le côté inférieur
Intuition
La formule ne nécessite que le plus petit des deux murs. Si tu peux prouver que le mur de gauche est le plus petit à un certain indice, tu n’as jamais besoin du mur de droite à cet indice. Deux pointeurs te donnent cette preuve. Place left à l’indice 0 et right au dernier indice, et garde leftMax et rightMax, la barre la plus haute que chaque pointeur a dépassée jusque-là, y compris la barre sur laquelle il se trouve.
L’invariant : chaque barre que les pointeurs ont déjà dépassée n’est pas plus haute que la plus haute des deux barres sur lesquelles ils se trouvent maintenant. Il est vérifié parce que tu déplaces toujours le pointeur situé sur la barre la plus basse ; un pointeur ne passe donc jamais devant une barre plus haute que celle sous l’autre pointeur.
Supposons maintenant que height[left] < height[right]. D’après l’invariant, leftMax est inférieur ou égal à height[right], et height[right] est lui-même une barre située à droite de left. Le véritable mur de droite de left est donc au moins aussi haut que leftMax, et le niveau à left est exactement leftMax, quelle que soit la barre située entre les pointeurs. Ajoute leftMax - height[left] et déplace left d’un pas vers la droite. Lorsque height[right] est la barre la plus basse ou qu’elle est de même hauteur, fais l’opération symétrique du côté droit. Mets à jour le maximum courant avant d’ajouter l’eau, afin que la barre sous le pointeur compte comme son propre mur et que la quantité d’eau ne soit jamais négative.
Parcours [0, 3, 1, 0, 2, 5, 1, 2]. Les pointeurs commencent sur 0 et 2 : celui de gauche est plus bas, il retient 0. Ensuite, 3 contre 2 : celui de droite est plus bas, rightMax devient 2, il retient 0. Puis 3 contre 1 : celui de droite est encore plus bas, le 1 retient 2-1 = 1. Puis 3 contre 5 : celui de gauche est maintenant plus bas, leftMax vaut 3, le 3 retient 0, le 1 retient 2, le 0 retient 3 et le 2 retient 1. Les pointeurs se rejoignent au 5. Le total est 1 + 2 + 3 + 1 = 7, en un seul parcours et avec quatre variables.
Algorithme
- Définissez
left = 0,right = n-1, et définissezleftMax,rightMaxetwaterà 0. - Tant que
left < right, comparezheight[left]àheight[right]. - Si la barre de gauche est plus basse, augmentez
leftMaxjusqu’àheight[left]si nécessaire, ajoutezleftMax - height[left]et déplacezleftvers la droite. - Sinon, augmentez
rightMaxjusqu’àheight[right]si nécessaire, ajoutezrightMax - height[right]et déplacezrightvers la gauche. - Renvoie
waterlorsque les pointeurs se rejoignent ; la barre sur laquelle ils se rejoignent est la plus haute et ne retient rien.
def trap(height):
left, right = 0, len(height) - 1
left_max = right_max = 0 # tallest bar passed so far from each end
water = 0
while left < right:
if height[left] < height[right]:
# A bar taller than height[left] waits on the right, so left_max sets the level here.
left_max = max(left_max, height[left])
water += left_max - height[left]
left += 1
else:
# A bar at least as tall as height[right] waits on the left, so right_max sets the level.
right_max = max(right_max, height[right])
water += right_max - height[right]
right -= 1
return water
Pièges et cas limites
La formule est courte, et la plupart des mauvaises réponses viennent de l’ordre de deux lignes ou du côté vers lequel tu te déplaces.
- Ajouter l’eau avant de mettre à jour le maximum courant. Si
height[left]est supérieur àleftMax,leftMax - height[left]est négatif et le total diminue. Mets d’abord à jour le maximum, puis ajoute. - Déplacer le pointeur du côté de la barre la plus haute. Le niveau n’est connu que du côté le plus bas ; déplacer le côté le plus haut revient à utiliser un mur que tu n’as pas démontré. Sur
[4, 1, 3, 0, 5], cette version renvoie 4 au lieu de 8. - Ne regarder que les voisins les plus proches. Les murs d’une barre peuvent être éloignés : dans
[3, 0, 2, 0, 1, 0, 4], la barre de 1 retient l’eau jusqu’au niveau 3, déterminé par des barres situées respectivement quatre et deux positions plus loin. La réponse est 12. - Considérer les extrémités du tableau comme des murs. L’eau au-delà de la première ou de la dernière barre s’écoule, donc une seule barre, deux barres, ou une rangée qui ne fait que monter ou que descendre retient 0.
- Exclure la barre
ide ses propres parcours dans la méthode par force brute. Une barre plus haute que les deux côtés donne alors une quantité négative. Inclus-la, ou limite le résultat à 0. - Débordement dans une variante qui utilise une multiplication. Ici, la réponse atteint environ 2 × 10^9 (deux barres de 10^5 autour de 19,998 cases vides), ce qui tient encore dans un entier signé de 32 bits ; dans tes propres variantes, utilise des sommes sur 64 bits.
Questions fréquentes4
Quelle est la complexité temporelle du problème de collecte d’eau de pluie ?
La solution à deux pointeurs s’exécute en O(n) et utilise O(1) espace supplémentaire : à chaque étape, un pointeur se déplace vers l’intérieur, il y a donc n-1 étapes. La version avec les tableaux leftMax et rightMax s’exécute également en O(n), mais utilise O(n) espace. Parcourir les deux côtés depuis chaque barre prend O(n²), soit environ 4 × 10^8 lectures pour 2 × 10^4 barres.
Pourquoi la solution à deux pointeurs peut-elle déplacer le côté le plus court ?
Chaque barre déjà dépassée n’est pas plus haute que la plus haute des deux barres actuelles, car seul le pointeur le plus bas se déplace. Ainsi, lorsque la barre de gauche est plus basse, son maximum courant est inférieur ou égal à la barre de droite, et celle-ci constitue un véritable mur à sa droite. Le niveau au pointeur de gauche correspond à son maximum courant, quelles que soient les barres situées entre les pointeurs ; tu peux donc déterminer le volume pour cette barre et continuer.
Peut-on résoudre le problème de piégeage de l’eau de pluie avec une pile ?
Oui. Conserve une pile d’indices dont les hauteurs augmentent du bas vers le haut. Lorsqu’une barre plus haute que celle au sommet arrive, dépile l’indice du sommet : cette barre est le fond d’un bassin dont les parois sont la nouvelle barre au sommet de la pile et la barre actuelle. Ajoute (min(two walls) - floor) × (distance between the walls - 1), et continue à dépiler tant que la barre actuelle est plus haute. La pile calcule l’eau par couches horizontales plutôt que par colonnes, en O(n) temps et O(n) espace.
En quoi le problème de la collecte de l’eau de pluie diffère-t-il de celui du récipient contenant le plus d’eau ?
Dans Container With Most Water, tu choisis deux lignes et celles entre elles n’occupent pas d’espace : la réponse est donc un seul rectangle, le plus grand possible. Ici, chaque barre est pleine, l’eau repose au-dessus de chaque barre et la réponse est la somme de toutes les barres. Les deux problèmes utilisent deux pointeurs qui déplacent le côté le plus bas, pour la même raison : le résultat du côté le plus bas est déjà déterminé.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
Python
def trap(height):
# Écrivez le code iciCas 1
Cas 2
Cas 3
Entrée
height = [0, 3, 1, 0, 2, 5, 1, 2]
Attendu
7