Implémentation en Python de la @IVlad la réponse de O(n) solution:
from collections import namedtuple
Info = namedtuple('Info', 'start height')
def max_rectangle_area(histogram):
"""Find the area of the largest rectangle that fits entirely under
the histogram.
"""
stack = []
top = lambda: stack[-1]
max_area = 0
pos = 0 # current position in the histogram
for pos, height in enumerate(histogram):
start = pos # position where rectangle starts
while True:
if not stack or height > top().height:
stack.append(Info(start, height)) # push
elif stack and height < top().height:
max_area = max(max_area, top().height*(pos-top().start))
start, _ = stack.pop()
continue
break # height == top().height goes here
pos += 1
for start, height in stack:
max_area = max(max_area, height*(pos-start))
return max_area
Exemple:
>>> f = max_rectangle_area
>>> f([5,3,1])
6
>>> f([1,3,5])
6
>>> f([3,1,5])
5
>>> f([4,8,3,2,0])
9
>>> f([4,8,3,1,1,0])
9
Copier-coller de l'algorithme de description (dans le cas de la page descend):
Nous traitons les éléments de la
de gauche à droite et de maintenir un
la pile de l'information au sujet démarré, mais
encore inachevée subhistograms. Chaque fois que
un élément nouveau arrive, il est soumis
les règles suivantes. Si la pile
est vide, nous ouvrons une nouvelle subproblem par
en poussant l'élément sur la pile.
Sinon on la compare à celle de l'élément
en haut de la pile. Si la nouvelle est
plus nous avons de nouveau pousser. Si la nouvelle
l'un est l'égalité de nous ignorer. Dans tous ces
cas, nous continuons avec la nouvelle
de l'élément. Si la nouvelle est moins, nous
terminer le plus haut subproblem par
la mise à jour de la superficie maximale w.r.t. l'
l'élément au sommet de la pile. Ensuite,
nous rejetons l'élément en haut, et
répétez la procédure de maintien de la
nouvel élément. De cette façon, tous les
sous-problèmes sont finis jusqu'à ce que le
la pile est vide, ou ses
l'élément est inférieure ou égale à la
élément nouveau, conduisant à des actions
décrit ci-dessus. Si tous les éléments ont
été traitées, et la pile n'est pas
encore vide, nous avons fini le reste
sous-problèmes en mettant à jour le maximum
la zone w.r.t. pour les éléments à l'
haut.
Pour la mise à jour de w.r.t. un élément, nous
trouver le plus grand rectangle qui
comprend l'élément. Observer qu'une
mise à jour de la superficie maximale est assurée
pour tous les éléments à l'exception de ceux
sauté. Si un élément est ignoré,
cependant, il a le même plus grand
rectangle comme l'élément en haut de la
pile à ce moment que sera
mis à jour plus tard. La hauteur de la
plus grand rectangle est, bien sûr, la
la valeur de l'élément. Au moment de la
la mise à jour, nous savons dans quelle mesure l'
plus grand rectangle s'étend vers la droite
de l'élément, parce qu'alors, pour la
première fois, un nouvel élément avec le plus petit
la hauteur est arrivé. L'information, comment
de loin le plus grand rectangle s'étend à
la gauche de l'élément, est disponible
si nous conservons sur la pile, trop.
Nous avons donc réviser la procédure
décrit ci-dessus. Si un nouvel élément est
poussé immédiatement, soit parce que la
la pile est vide ou qu'il est supérieur à
l'élément supérieur de la pile, la
plus grand rectangle contenant
s'étend vers la gauche pas plus loin que
l'élément en cours. S'il est poussé
après plusieurs éléments ont été
sauté hors de la pile, parce que c'est
moins de ces éléments, le plus grand
rectangle contenant elle s'étend à l'
gauche aussi loin que celle de la plupart des
récemment sauté élément.
Chaque élément est poussé et a sauté à
plus d'une fois et à chaque étape de la
procédure au moins un élément est
poussé ou de maïs. Étant donné que le montant de
de travail pour les décisions et la mise à jour
est constante, la complexité de la
l'algorithme est O(n) par amorti
de l'analyse.
