46. Largest Rectangle in Histogram
Choose consecutive histogram bars and a rectangle whose height fits under every chosen bar. Return the greatest possible area over all choices of consecutive bars.
The shortest bar limits a chosen rectangle's height, while the number of chosen bars determines its width. The rectangle cannot skip a short bar in the middle.
Example 1
Input
[2,1,5,6,2,3]
Output
10
Explanation: Bars at indices two and three support height five across width two.
Example 2
Input
[2,2,2]
Output
6
Explanation: Equal-height ownership reaches the full width when the final representative is flushed.
Constraints
0 <= heights.length <= 1050 <= heights[i] <= 231 - 1
Hints
Hint 1
When does a new bar prove a pending height cannot continue right?
Hint 2
After a pop, which two boundaries enclose its valid span?
Hint 3
Compute height*(i-left-1), transfer equal representatives, and flush with a virtual sentinel.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Pop completed spans at smaller right boundaries
[2,1,5,6,2,3]
10