Largest Rectangle in Histogram

Ein Rechteck überdeckt eine Reihe benachbarter Balken von start bis end, und seine Höhe ist durch den niedrigsten Balken in der Reihe begrenzt. Probiere also jede Reihe aus. Fixiere start, vergrößere dann end Balken für Balken und behalte die bisher niedrigste Höhe bei. Die Fläche des größten Rechtecks über dieser Reihe beträgt lowest × (end-start+1).

In [2, 5, 6, 3, 4, 1] beginnst du bei der 5. Die Reihen ergeben 5 × 1 = 5, dann 5 × 2 = 10 mit der 6, dann 3 × 3 = 9, sobald die 3 dazukommt, 3 × 4 = 12 mit der 4 und 1 × 5 = 5 mit der 1. Die 12 ist die Antwort. Wenn du lowest aktualisierst, während die Reihe wächst, bleibt jeder Schritt bei O(1), sodass du die Reihe nie erneut nach ihrem Minimum durchsuchen musst.

Das Verfahren ist korrekt, weil jedes Rechteck über einer Reihe liegt und für eine feste Reihe das höchste passende Rechteck genau so hoch ist wie der niedrigste Balken. Es ist langsam, weil es n(n+1)/2 Reihen gibt: etwa 2 × 10^8 bei 2 × 10^4 Balken, und diese Anzahl hängt überhaupt nicht von den Höhen ab. Die meisten dieser Reihen werden lange vor ihrem Ende durch einen niedrigen Balken begrenzt, doch der Brute-Force-Ansatz erweitert sie trotzdem weiter.

Kehre die Suche um. Im optimalen Rechteck ist mindestens ein Balken darunter genau so hoch wie das Rechteck; andernfalls könntest du das Rechteck höher machen. Die Antwort ist also das Maximum über alle Balken i für ein Rechteck mit genau der Höhe heights[i], das sich so weit wie möglich ausdehnt. Es reicht bis zu einem auf jeder Seite strikt niedrigeren Balken. Nenne ihre Indizes left[i] und right[i]; gibt es keinen, verwende -1 beziehungsweise n. Das Rechteck umfasst die Balken strikt zwischen ihnen: Die Breite beträgt right[i]-left[i]-1. Damit gibt es n Kandidaten statt n²/2.

Um left[i] für jeden Balken zu finden, gehst du von links nach rechts und verwendest einen Stapel mit Indizes, deren Balkenhöhen von unten nach oben strikt ansteigen. Sobald Balken i erreicht wird, entfernst du alle Indizes, deren Balken mindestens so hoch ist wie heights[i]. Diese Balken können für i oder für einen späteren Balken nie der nächste niedrigere Balken sein, denn i ist näher und nicht höher. Was oben übrig bleibt, ist der nächste niedrigere Balken links davon. Dann legst du i auf den Stapel. Derselbe Durchlauf von rechts nach links ergibt right[i].

Für [2, 5, 6, 3, 4, 1] ergeben die Durchläufe left = [-1, 0, 1, 0, 3, -1] und right = [5, 3, 3, 5, 5, 6]. Der Balken mit Höhe 3 an Index 3 wird links vom Balken mit Höhe 2 an Index 0 und rechts vom Balken mit Höhe 1 an Index 5 begrenzt; sein Rechteck hat also die Fläche 3 × (5-0-1) = 12. Die 6 ist von ihren Nachbarn eingeschlossen und ergibt nur 6 × 1.

Jeder Index wird in jedem Durchlauf einmal auf den Stapel gelegt und höchstens einmal entfernt. Daher benötigen beide Durchläufe O(n), auch wenn ein Balken viele Elemente entfernen kann. Dafür sind zwei zusätzliche Arrays nötig.

Der Durchlauf von links nach rechts sieht bereits jede rechte Grenze, verwirft sie aber. Wenn Balken i Balken t aus dem Stapel entfernt, ist heights[i] nicht höher als heights[t], also ist i die Stelle, an der das Rechteck von t rechts endet. Und der Index, der im Stapel unter t liegt, ist die Stelle, an der es links endet. Miss also das Rechteck genau in dem Moment, in dem du den Balken entfernst: heights[t] × (i - below - 1), wobei below der neue oberste Index im Stapel ist oder -1, wenn der Stapel jetzt leer ist.

Die Invariante: Die Höhen im Stapel steigen von unten nach oben streng an, und der Index unter jedem Eintrag ist der nächstgelegene Balken links davon, der niedriger ist. Jeder Balken zwischen den beiden wurde auf dem Weg entfernt, entweder durch den Eintrag selbst oder durch einen Balken, den der Eintrag später entfernt hat. Keiner davon ist also niedriger als der Eintrag. Balken, die nie entfernt werden, reichen bis ganz ans Ende. Deshalb verarbeitest du nach dem letzten Balken noch einen Balken mit Höhe 0. Er ist niedriger als alle anderen und leert den Stapel.

Gehen wir [2, 5, 6, 3, 4, 1] durch. Füge 2, 5 und 6 hinzu: Der Stapel enthält die Indizes [0, 1, 2]. Die 3 am Index 3 entfernt die 6 (Fläche 6 × (3-1-1) = 6) und die 5 (Fläche 5 × (3-0-1) = 10), hält dann bei der 2 an und wird hinzugefügt. Füge die 4 hinzu. Die 1 am Index 5 entfernt die 4 (Fläche 4), dann die 3, deren Rechteck von Index 1 bis 4 reicht: 3 × (5-0-1) = 12. Sie entfernt auch die 2 (2 × 5 = 10; der Stapel ist leer, also beträgt die Breite 5). Die abschließende 0 entfernt die 1 (1 × 6 = 6). Das Maximum ist 12.

Wenn beim Entfernen >= verwendet wird, kann ein gleich hoher Balken einen anderen Balken zu früh stoppen. Das ist unproblematisch: Der gleich hohe Balken nimmt seinen Platz im Stapel ein, übernimmt dieselbe linke Grenze und umfasst später, wenn er entfernt wird, den gesamten Abschnitt. Bei [3, 3, 3, 3] ergeben die ersten drei 3en die Breiten 1, 2 und 3; die letzte wird von der abschließenden 0 mit Breite 4 entfernt, was 12 ergibt.