84. Largest Rectangle in Histogram #

Problem #

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

Example:

Input: [2,1,5,6,2,3]
Output: 10

Problem Summary #

Given the height of each histogram bar, find the rectangle with the largest area among these histogram bars and output the area of the rectangle.

Solution Approach #

Use a monotonic stack to sequentially store the indices of the histogram heights. Once a height smaller than the stack-top element appears, pop the stack-top element and separately calculate the height of the rectangle for this stack-top element. Then stop here (the i– in the outer loop, followed by ++, is equivalent to stopping here), and continue popping the element before the current largest stack top, that is, continuously pop the 2 largest ones, using the slightly smaller one as the edge of the rectangle, with width 2 to calculate the area… If the height represented by the index stopped here is always smaller than the elements in the stack, keep popping, and take the last height greater than the current index as the edge of the rectangle. The width is the difference between the last height greater than the current index and the current index i. After calculating the area, continuously update maxArea.

Code #

package leetcode

func largestRectangleArea(heights []int) int {
	maxArea := 0
	n := len(heights) + 2
	// Add a sentry at the beginning and the end
	getHeight := func(i int) int {
		if i == 0 || n-1 == i {
			return 0
		}
		return heights[i-1]
	}
	st := make([]int, 0, n/2)
	for i := 0; i < n; i++ {
		for len(st) > 0 && getHeight(st[len(st)-1]) > getHeight(i) {
			// pop stack
			idx := st[len(st)-1]
			st = st[:len(st)-1]
			maxArea = max(maxArea, getHeight(idx)*(i-st[len(st)-1]-1))
		}
		// push stack
		st = append(st, i)
	}
	return maxArea
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}