Alle Herausforderungen
Schwierig 1 gelöst 100.0% Erfolgsquote

Largest Rectangle in a Histogram

Find the largest rectangle that fits under a histogram.

Das lernst du

  • Das breiteste Rechteck jedes Balkens finden
  • Einen Stack steigender Höhen verwenden
  • Das Problem in linearer Zeit lösen

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

Beispiel 1
Eingabe:
heights = [2, 1, 5, 6, 2, 3]

Erwartete Ausgabe:
expected = 10
Eingabe:
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.

Beispiel 2
Eingabe:
heights = [4]

Erwartete Ausgabe:
expected = 4
Eingabe:
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.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

# Coder Sprache Zeit Speicher KI-Bewertung Lösung
1 ННикита Python 996 ms - 5/5 Code ansehen

Von anderen lernen

Community-Lösungen

Achtung Spoiler: 1 vollständige Lösung unten Versuche es zuerst selbst zu lösen. Du kannst trotzdem einen Blick auf den Code und die KI-Reviews anderer Entwickler werfen. Melde dich an und löse die Aufgabe, um an der Diskussion teilzunehmen.