Problème
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.
Contraintes
0 ≤ length ≤ 200,000; 0 ≤ height ≤ 1,000,000,000
Exemples
Entrée :
heights = [2, 1, 5, 6, 2, 3]
Sortie attendue :
expected = 10Entrée :
std::vector<long long> heights = {2, 1, 5, 6, 2, 3};
Sortie attendue :
long long expected = 10;Entrée :
long[] heights = new long[] {2, 1, 5, 6, 2, 3};
Sortie attendue :
long expected = 10;Explication
Bars 5 and 6 together give a 2-wide rectangle of height 5: area 10.
Entrée :
heights = [4]
Sortie attendue :
expected = 4Entrée :
std::vector<long long> heights = {4};
Sortie attendue :
long long expected = 4;Entrée :
long[] heights = new long[] {4};
Sortie attendue :
long expected = 4;Explication
A single bar of height 4 has area 4.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Le meilleur rectangle pour une barre dépend de la distance qu’elle peut s’étendre avant qu’une barre plus courte ne bloque.
Indice 2
Utilise une pile monotone croissante pour trouver, pour chaque barre, sa barre plus petite la plus proche des deux côtés.
Indice 3
N’oublie pas les barres qui ne sont jamais dépilées avant la fin, et gère les hauteurs égales de façon cohérente.
Complexité attendue
temps O(n), espace supplémentaire O(n)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.