Définition — Problème de collecte d'eau de pluie Étant donné un tableau où chaque élément représente la hauteur d'une tour, s'il commence à pleuvoir, quelle est la quantité totale d'eau pouvant être collectée entre les tours ?
On suppose que la largeur de chaque tour est 1.
On suppose que la largeur de chaque tour est 1.
Exemple
Entrée
T = [1, 5, 2, 3, 1, 7, 2, 4]
Sortie
11
Explication : La quantité d'eau au-dessus de chaque tour (de gauche à droite) : 0 + 0 + 3 + 2 + 4 + 0 + 2 + 0 = 11 unités.
Contraintes
- 1 ≤ n ≤ 10⁵
- 0 ≤ T[i] ≤ 10⁴
Analyse du problème
Observation clé — Eau au-dessus d'une tour Pour qu'il y ait de l'eau au-dessus de la tour d'indice i, sa hauteur doit être inférieure à celle d'au moins une tour à sa gauche et à sa droite.
La quantité d'eau exacte au-dessus de la tour i est :
où
La quantité d'eau exacte au-dessus de la tour i est :
eau[i] = max(0, min(max_gauche[i], max_droite[i]) − T[i]) où
max_gauche[i] = hauteur maximale à gauche de i (i inclus), et max_droite[i] = hauteur maximale à droite de i (i inclus).Illustration — Tour à l'indice 2 (hauteur = 2)
| Indice i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| T[i] | 1 | 5 | 2 | 3 | 1 | 7 | 2 | 4 |
| max_gauche | 1 | 5 | 5 | 5 | 5 | 7 | 7 | 7 |
| max_droite | 7 | 7 | 7 | 7 | 7 | 7 | 4 | 4 |
| eau[i] | 0 | 0 | 3 | 2 | 4 | 0 | 2 | 0 |
Tour 2 : min(5, 7) − 2 = 5 − 2 = 3 unités d'eau. Total = 0+0+3+2+4+0+2+0 = 11.
Solution — Tableaux de préfixes/suffixes
Procédure en 3 étapes
- Précalculer
max_gauche[i]= max de T[0..i] (parcours gauche → droite). - Précalculer
max_droite[i]= max de T[i..n-1] (parcours droite → gauche). - Pour chaque tour : accumuler
min(max_gauche[i], max_droite[i]) − T[i].
Algorithme collecter(T, n):
Créer max_gauche[0..n-1] et max_droite[0..n-1]
// Étape 1 : max des hauteurs à gauche (préfixe)
max_gauche[0] ← T[0]
Pour i de 1 à n-1 :
max_gauche[i] ← max(max_gauche[i-1], T[i])
// Étape 2 : max des hauteurs à droite (suffixe)
max_droite[n-1] ← T[n-1]
Pour i de n-2 à 0 :
max_droite[i] ← max(max_droite[i+1], T[i])
// Étape 3 : accumuler l'eau
quantite ← 0
Pour i de 0 à n-1 :
quantite ← quantite + min(max_gauche[i], max_droite[i]) − T[i]
Retourner quantitedef collecter(tab):
"""
Collecte d'eau de pluie — Tableaux de préfixes/suffixes.
Complexité : O(n) temps, O(n) espace.
"""
n = len(tab)
max_gauche = [0] * n
max_droite = [0] * n
quantite = 0
# Étape 1 : max à gauche (préfixe)
max_gauche[0] = tab[0]
for i in range(1, n):
max_gauche[i] = max(max_gauche[i - 1], tab[i])
# Étape 2 : max à droite (suffixe)
max_droite[n - 1] = tab[n - 1]
for i in range(n - 2, -1, -1):
max_droite[i] = max(max_droite[i + 1], tab[i])
# Étape 3 : calculer l'eau au-dessus de chaque tour
for i in range(n):
quantite += min(max_gauche[i], max_droite[i]) - tab[i]
return quantite
# Test
print(collecter([1, 5, 2, 3, 1, 7, 2, 4])) # 11Sortie
11
Complexité — Solution par préfixes/suffixes
| Critère | Valeur | Justification |
|---|---|---|
| Temps | O(n) | 3 parcours linéaires indépendants |
| Espace | O(n) | Deux tableaux auxiliaires de taille n |
Optimisation — Deux pointeurs, O(1) espace On peut éliminer les deux tableaux auxiliaires en utilisant deux pointeurs
gauche et droitequi se rapprochent depuis les extrémités. On traite toujours le côté dont le max est le plus faible :def collecter_v2(tab):
"""Deux pointeurs — O(n) temps, O(1) espace."""
gauche, droite = 0, len(tab) - 1
max_g, max_d = 0, 0
quantite = 0
while gauche < droite:
if tab[gauche] < tab[droite]:
if tab[gauche] >= max_g:
max_g = tab[gauche]
else:
quantite += max_g - tab[gauche]
gauche += 1
else:
if tab[droite] >= max_d:
max_d = tab[droite]
else:
quantite += max_d - tab[droite]
droite -= 1
return quantite
print(collecter_v2([1, 5, 2, 3, 1, 7, 2, 4])) # 11
Sortie
// La sortie apparaîtra ici…
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.