Largest rectangular area in a histogram
Problem
heights[i] is the height of a bar of width 1. Return the area of the largest rectangle that fits entirely inside the histogram.
Example 1
Input: [2, 1, 5, 6, 2, 3] Output: 10
The bars of height 5 and 6 give a 5 × 2 rectangle.
Also asked as: Largest rectangular Area in Histogram
Test cases
Case 1
Input: [2,1,5,6,2,3] Expected: 10
Case 2
Input: [2,4] Expected: 4
Case 3
Input: [6,2,5,4,5,1,6] Expected: 12
View solutionHide solution1 approach
1. Monotonic increasing stack of indices
Time O(n)Space O(n)
When a shorter bar appears, pop taller bars; each popped bar’s max rectangle uses it as the height, bounded by the new bar and the stack’s new top.
function largestRectangleArea(h) { const st = []; let best = 0; for (let i = 0; i <= h.length; i++) { const cur = i === h.length ? 0 : h[i]; while (st.length && h[st[st.length - 1]] >= cur) { const height = h[st.pop()]; const width = st.length ? i - st[st.length - 1] - 1 : i; best = Math.max(best, height * width); } st.push(i); } return best;}