Stacks and Queues Monotonic stack
218. Largest Rectangle in Histogram
You are given an array of non-negative integers heights. Each value is the height of a bar 1 unit wide, and
the bars stand side by side in order on flat ground, with no gaps between them. Return the area of the
largest rectangle that fits under the tops of the bars.
The rectangle stands on the ground and covers a run of one or more neighbouring bars, whole bars only. It can be as tall as the shortest bar in that run and no taller. So its area is the number of bars it covers times the height of the shortest of them. A height of 0 means there is no bar at that position, only ground.
This is Example 1, heights = [2,4,5,3,1,3], with its largest rectangle drawn in. The rectangle covers bars
1 to 3 and is 3 units high, so its area is 9.
Example 1
Input: heights = [2, 4, 5, 3, 1, 3]
9Explanation: Bars 1 to 3 are 4, 5 and 3 high, so a rectangle across them can be 3 high, and its area is 3 × 3 = 9. The two tallest bars on their own make only 2 × 4 = 8, and all six bars make 6 × 1 = 6.
Example 2
Input: heights = [4, 2, 3, 2]
8Explanation: No bar is shorter than 2, so a rectangle 2 high fits across all four bars and makes 4 × 2 = 8. Every narrower run does worse: the best of them are the first three bars and the last three, and each makes 3 × 2 = 6.
Example 3
Input: heights = [0, 9, 0, 4, 4, 0]
9Explanation: A rectangle that covers a 0 is 0 high, so the zeros split the bars into groups. The 9 on its own makes 9, which beats the two 4s, 2 × 4 = 8.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ heights.length ≤ 1050 ≤ heights[i] ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.