Collecter l'eau de pluie entre les tours

Do you have difficulties understanding French courses? visit our English version Click here

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
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 M. ESSADDOUKI

Many people realize their hearts desires late in life. Continue learning, never stop striving and keep your curiosity sharp, and you will never become too old to appreciate life.

0 Commentaire(s)

Pour laisser un commentaire vous devez avoir un compte Inscription, ou Se connecter