Trapping Rain Water
Une rangée de barres se tient côte à côte, chacune d’une unité de large : height[i] est la hauteur de la barre i. L’eau de pluie s’accumule dans les creux entre les barres. L’eau ne reste au-dessus d’une barre que 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. Retourne le nombre total d’unités d’eau retenues par la rangée.
Fonction
- heightinteger-array
- la hauteur de chaque barre, de gauche à droite
- Renvoieinteger
- le nombre total d’unités d’eau retenues
Contraintes
1 ≤ height.length ≤ 2 × 1040 ≤ height[i] ≤ 105- Chaque barre a une largeur d’une unité, et l’eau ne reste pas au-delà de la première ou 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, le niveau est 3 : 2 unités au-dessus du 1, 3 au-dessus du 0, 1 au-dessus du 2. Le 1 suivant se trouve entre le 5 et un 2, donc il vaut 1. Cela fait 7.
- Entrée
- height = [4, 1, 3, 0, 5]
- Sortie
- 8
- Explication
- Le mur le plus bas est le 4, donc le creux se remplit jusqu’au niveau 4 : 3 unités au-dessus du 1, 1 au-dessus du 3, 4 au-dessus du 0, ce qui fait 8. L’eau déborde par-dessus le 4 avant que le 5 n’entre en jeu.
- Entrée
- height = [1, 2, 4, 2, 1]
- Sortie
- 0
- Explication
- Les barres montent jusqu’à 4, puis redescendent. Chaque barre a un côté où rien ne la dépasse en hauteur, alors l’eau s’écoule et la réponse est 0.
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 la rangée entière et regarde une seule barre. Jusqu’où 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 maximums. Place un pointeur à chaque extrémité et conserve 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 et déplace ce pointeur vers l’intérieur. Arrête-toi lorsque les pointeurs se rejoignent.
Solution
L’eau au-dessus d’une barre dépend des barres qui peuvent être éloignées des deux côtés. Son niveau correspond à la plus petite des deux hauteurs maximales, celle à sa gauche et celle à sa droite, et la barre retient cette hauteur moins sa propre hauteur.
Parcours les deux côtés de chaque barre
Correcte, mais ne termine pas sur les plus gros tests
Intuition
Pour chaque barre i, parcourez de 0 à i pour trouver la barre la plus haute à gauche, et de i jusqu’à la fin pour trouver la plus haute à droite, puis ajoutez min(leftMax, rightMax) - height[i]. Inclure la barre i dans les deux parcours évite que la quantité devienne négative et donne 0 pour les barres aux extrémités.
Chaque barre parcourt toute la rangée : n = 2 × 10^4 signifie 4 × 10^8 lectures, dont la plupart répètent le parcours de la barre précédente.
Algorithme
- Définissez
waterà 0. - Pour chaque index
i, parcourez les indices de 0 àipour trouverleftMax. - Parcourez les indices de
ijusqu'au dernier index pour trouverrightMax. - Ajoutez
min(leftMax, rightMax) - height[i]àwater. - Retournez
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 barre la plus haute entre 0 et i est la plus grande entre la barre la plus haute entre 0 et i-1 et height[i]. Ainsi, un passage de gauche à droite remplit leftMax, chaque entrée étant construite à partir de la précédente, et un passage de droite à gauche remplit rightMax. Un troisième passage applique la formule.
Pour [0, 3, 1, 0, 2, 5, 1, 2], les niveaux min(leftMax[i], rightMax[i]) sont [0, 3, 3, 3, 3, 5, 2, 2]. En soustrayant les hauteurs, on obtient [0, 0, 2, 3, 1, 0, 1, 0], dont la somme est 7. Le temps d’exécution est O(n), au prix de deux tableaux de n nombres.
Algorithme
- Remplissez
leftMaxde gauche à droite :leftMax[0] = height[0], puisleftMax[i] = max(leftMax[i-1], height[i]). - Remplissez
rightMaxde droite à gauche :rightMax[n-1] = height[n-1], puisrightMax[i] = max(rightMax[i+1], height[i]). - Pour chaque indice, ajoutez
min(leftMax[i], rightMax[i]) - height[i]au total. - Retournez 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 mur le plus bas, et deux pointeurs permettent de prouver lequel c’est. Place left à 0 et right au dernier indice, garde une trace de leftMax et rightMax, la barre la plus haute dépassée par chaque pointeur, y compris celle sous lequel il se trouve, et déplace toujours le pointeur situé sur la barre la plus basse. Alors chaque barre déjà dépassée n’est pas plus haute que la plus haute des deux barres actuelles, car un pointeur ne dépasse une barre que si celle-ci n’est pas plus haute que celle sous l’autre pointeur.
Supposons que height[left] < height[right]. D’après l’invariant, leftMax est inférieur ou égal à height[right], une barre située à droite de left. Le mur droit de left est donc au moins aussi haut que leftMax, et le niveau auquel se trouve l’eau est exactement leftMax, quelle que soit la hauteur de ce qui se trouve entre les pointeurs. Lorsque la barre de droite est plus basse ou de même hauteur, le raisonnement symétrique permet de trancher pour right.
Algorithme
- Définis
left = 0,right = n-1, etleftMax,rightMaxetwaterà 0. - Tant que
left < right: siheight[left] < height[right], augmenteleftMaxjusqu’àheight[left]si nécessaire, ajouteleftMax - height[left]et déplaceleftvers la droite. - Sinon, fais de même du côté droit et déplace
rightvers la gauche. - Retourne
water. La barre où les pointeurs se rejoignent est la plus haute et ne retient pas d’eau.
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
- Ajouter l’eau avant de mettre à jour le maximum courant. Quand
height[left]est supérieur àleftMax, la quantité est négative et le total diminue. - Déplacer le pointeur du côté de la barre la plus haute, dont le niveau n’est pas établi. Sur
[4, 1, 3, 0, 5], cette version renvoie 4 au lieu de 8. - Ne regarder que les voisins les plus proches. Dans
[3, 0, 2, 0, 1, 0, 4], la barre de hauteur 1 se remplit jusqu’au niveau 3, déterminé par des barres situées à quatre et deux positions de distance ; la réponse est 12. - Considérer les extrémités du tableau comme des murs. L’eau s’en écoule, donc une barre, deux barres ou une rangée qui ne fait que monter ou que descendre retient 0.
Questions fréquentes3
Quelle est la complexité temporelle du problème de piégeage de l’eau de pluie ?
La solution à deux pointeurs s’exécute en O(n) et utilise O(1) espace supplémentaire, puisque chaque étape déplace un pointeur vers l’intérieur. 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²).
Peut-on résoudre le problème de l’eau de pluie piégée à l’aide d’une pile ?
Oui. Garde une pile d’indices dont les hauteurs sont décroissantes. Lorsqu’une barre plus haute arrive, dépile le sommet : c’est le fond d’un bassin délimité par le nouveau sommet et la barre actuelle. Ajoute (min(two walls) - floor) × (distance between the walls - 1) et continue à dépiler. Cela remplit l’eau par couches horizontales, en O(n) temps et espace.
En quoi Trapping Rain Water diffère-t-il de Container With Most Water ?
Dans « Container With Most Water », les lignes n’occupent aucun espace et la réponse est le plus grand rectangle entre deux lignes. Ici, chaque barre est pleine et la réponse correspond à la somme de l’eau sur toutes les barres. Dans les deux cas, on déplace le côté le plus bas pour la même raison : son résultat 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.
def trap(height):
# Écrivez le code iciTest #1
Test #2
Test #3
Argument
height = [0, 3, 1, 0, 2, 5, 1, 2]
Résultat attendu
7