Collecter l'eau de pluie entre les tours
Etant donné un tableau où chaque élément représente la hauteur d'une tour, s'il commence à pleuvoir, quelle est la quantité d'eau pouvant être collectée entre les tours?
On suppose que la largeur de chaque tour est 1
Exemple :T=[1, 5, 2, 3, 1, 7, 2, 4]
La réponse est : 11
Procedure :
- pour chaque tour, nous essayons de déterminer s'il y a une unité d'eau de pluie au-dessus, si oui, quelle en est la quantité?
- continue d'ajouter la quantité d'eau de pluie fournie par chaque tour pour obtenir le total pour l'ensemble de tours donné
Pour une tour, comment pouvons-nous savoir s'il y a une unité d'eau de pluie dessus :
Pour que l'eau de pluie soit sur une tour, la hauteur de la tour doit être inférieure à celle d'une des tours voisines.
Exemple Tour 2
Exemple Tour 2
Quelle est la quantité maximale d'eau de pluie au-dessus de la tour actuelle :
tout d'abord en regardant à gauche de la tour actuelle et en recherchant la hauteur maximale(maxleft), puis en regardant à droite et en recherchant la hauteur maximale(maxright), et prenez
min(maxleft, maxright) - hauteur de la tour actuelle
- Créer deux tableaux de la même taille que le tableau original, maxgauche, maxdroite
- maxgauche[i] signifie la hauteur maximale sur le côté gauche de la tour tours[i], de même pour maxdroite[i]
- Calculer pour chaque tour rainwater =min(maxgauche[i],maxdroite[i])-tours[i]
def collecter(tab):
n=len(tab)
maxgauche = [0]*n
maxdroite = [0]*n
quantite = 0
maxgauche[0] = tab[0]
for i in range( 1, n):
maxgauche[i] = max(maxgauche[i-1], tab[i])
maxdroite[n-1] = tab[n-1]
for i in range(n-2, -1, -1):
maxdroite[i] = max(maxdroite[i+1], tab[i]);
for i in range(n):
quantite += min(maxgauche[i],maxdroite[i]) - tab[i]
return quantite
Partager ce cours avec tes amis :
Rédigé par
ESSADDOUKI
Mostafa
