Problem
A histogram has bars of width 1 with the given heights. Find the area of the largest rectangle that lies entirely within the bars. A monotonic stack gives an O(n) solution.
Implement largest_rectangle(heights).
Input
heights: Bar heights from left to right.
Output
Return the largest area.
Einschränkungen
0 ≤ length ≤ 200,000; 0 ≤ height ≤ 1,000,000,000
Beispiele
Eingabe:
heights = [2, 1, 5, 6, 2, 3]
Erwartete Ausgabe:
expected = 10Eingabe:
std::vector<long long> heights = {2, 1, 5, 6, 2, 3};
Erwartete Ausgabe:
long long expected = 10;Eingabe:
long[] heights = new long[] {2, 1, 5, 6, 2, 3};
Erwartete Ausgabe:
long expected = 10;Erläuterung
Bars 5 and 6 together give a 2-wide rectangle of height 5: area 10.
Eingabe:
heights = [4]
Erwartete Ausgabe:
expected = 4Eingabe:
std::vector<long long> heights = {4};
Erwartete Ausgabe:
long long expected = 4;Eingabe:
long[] heights = new long[] {4};
Erwartete Ausgabe:
long expected = 4;Erläuterung
A single bar of height 4 has area 4.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Das beste Rechteck für einen Balken hängt davon ab, wie weit es sich ausdehnen kann, bevor ein kleinerer Balken es stoppt.
Hinweis 2
Verwende einen monoton steigenden Stack, um für jeden Balken den nächsten kleineren Balken auf beiden Seiten zu finden.
Hinweis 3
Vergiss Balken nicht, die erst am Ende entfernt werden, und behandle gleiche Höhen konsequent.
Erwartete Komplexität
Zeit O(n), zusätzlicher Speicher O(n)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.