Largest Rectangle in Histogram

Un rectangle couvre une suite de barres voisines de start à end, et sa hauteur est limitée par la barre la plus basse de la suite. Il faut donc essayer chaque suite. Fixe start, puis augmente end d’une barre à la fois et conserve la hauteur minimale trouvée jusque-là. Le meilleur rectangle de cette suite a une aire de lowest × (end-start+1).

Dans [2, 5, 6, 3, 4, 1], commence par le 5. Les suites donnent 5 × 1 = 5, puis 5 × 2 = 10 avec le 6, puis 3 × 3 = 9 lorsque le 3 s’ajoute, 3 × 4 = 12 avec le 4, et 1 × 5 = 5 avec le 1. La réponse est 12. Mettre à jour lowest au fur et à mesure que la suite s’agrandit permet de garder chaque étape en O(1) ; tu n’as donc jamais à parcourir de nouveau une suite pour en trouver le minimum.

Cette méthode est correcte, car chaque rectangle se trouve au-dessus d’une suite, et pour une suite donnée, le rectangle le plus haut qui peut y tenir a exactement la hauteur de la barre la plus basse. Elle est lente, car il y a n(n+1)/2 suites : environ 2 × 10^8 pour 2 × 10^4 barres, et ce nombre ne dépend pas du tout des hauteurs. La plupart de ces suites sont limitées par une barre basse bien avant leur fin, mais la force brute continue quand même à les prolonger.

Renversez la recherche. Dans le meilleur rectangle, au moins une barre située dessous est exactement aussi haute que le rectangle ; sinon, vous pourriez agrandir le rectangle en hauteur. La réponse est donc le meilleur rectangle, parmi toutes les barres i, d’une hauteur exactement égale à heights[i] et aussi large que possible. Il s’étend jusqu’à rencontrer, de chaque côté, une barre strictement plus basse. Appelez leurs indices left[i] et right[i], en utilisant -1 et n s’il n’y en a pas. Le rectangle couvre les barres situées strictement entre elles : sa largeur est right[i]-left[i]-1. Cela donne n candidats au lieu de n²/2.

Pour trouver left[i] pour chaque barre, parcourez le tableau de gauche à droite en conservant une pile d’indices dont les hauteurs augmentent strictement du bas vers le haut. Lorsque la barre i arrive, dépilez chaque indice dont la barre est au moins aussi haute que heights[i]. Ces barres ne peuvent jamais être la barre plus basse la plus proche à gauche de i ni d’aucune barre suivante, car i est plus proche et pas plus haut. L’indice qui reste au sommet est celui de la barre plus basse la plus proche à gauche. Empilez ensuite i. Le même parcours de droite à gauche donne right[i].

Pour [2, 5, 6, 3, 4, 1], les parcours donnent left = [-1, 0, 1, 0, 3, -1] et right = [5, 3, 3, 5, 5, 6]. La barre de hauteur 3 à l’indice 3 est bloquée par celle de hauteur 2 à l’indice 0 et celle de hauteur 1 à l’indice 5 ; son rectangle mesure donc 3 × (5-0-1) = 12. La barre de hauteur 6 est encadrée par ses voisines et ne donne que 6 × 1.

Chaque indice est empilé une fois et dépilé au plus une fois au cours de chaque parcours. Les deux parcours sont donc en O(n), même si une barre peut en dépiler beaucoup d’autres. Le coût à payer est celui de deux tableaux supplémentaires.

Le parcours de gauche à droite voit déjà chaque limite droite ; il l’ignore. Quand la barre i dépile la barre t, heights[i] n’est pas supérieure à heights[t], donc i est l’endroit où le rectangle de t s’arrête à droite. Et l’indice qui se trouve sous t dans la pile est l’endroit où il s’arrête à gauche. Il faut donc mesurer le rectangle au moment du dépilement : heights[t] × (i - below - 1), où below est le nouvel élément au sommet de la pile, ou -1 si la pile est maintenant vide.

L’invariant : les hauteurs de la pile augmentent strictement du bas vers le haut, et l’indice sous chaque entrée est la barre la plus proche à sa gauche dont la hauteur est inférieure à la sienne. Chaque barre située entre les deux a été dépilée en chemin, soit par l’entrée elle-même, soit par une barre que l’entrée a dépilée plus tard ; aucune d’elles n’est donc plus petite que l’entrée. Les barres qui ne sont jamais dépilées vont jusqu’au bout, donc après avoir traité la dernière barre, on traite une barre supplémentaire de hauteur 0. Elle est plus petite que toutes les autres et vide la pile.

Parcourons [2, 5, 6, 3, 4, 1]. Empilons 2, 5 et 6 : la pile contient les indices [0, 1, 2]. Le 3 à l’indice 3 dépile le 6 (aire 6 × (3-1-1) = 6) et le 5 (aire 5 × (3-0-1) = 10), puis s’arrête au 2 et est empilé. Empilons le 4. Le 1 à l’indice 5 dépile le 4 (aire 4), puis le 3, dont le rectangle va de l’indice 1 à l’indice 4 : 3 × (5-0-1) = 12. Il dépile aussi le 2 (2 × 5 = 10 ; la pile est vide, donc la largeur est 5). Le 0 final dépile le 1 (1 × 6 = 6). Le maximum est 12.

Dépiler sur >= signifie qu’une barre de même hauteur peut arrêter une barre prématurément. C’est sans risque : la barre de même hauteur prend sa place dans la pile, conserve la même limite gauche et, lorsqu’elle est dépilée plus tard, son rectangle couvre toute la série. Dans [3, 3, 3, 3], les trois premiers 3 enregistrent des largeurs de 1, 2 et 3, et le dernier est dépilé par le 0 final avec une largeur de 4, ce qui donne 12.