84. Largest Rectangle in Histogram

LeetCode 84. Largest Rectangle in Histogram

Description

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

Input: heights = [2,4]
Output: 4

Constraints:

• 1 <= heights.length <= 10^5

• 0 <= heights[i] <= 10^4

Tags

Array, Stack

Solution

We use a monostack to keep track of all indices where the height is taller than the height at stack top index. If the incoming height is shorter than the stack top's, we pop the stack, calculate the area which equals to height[popedIndex] * (i-(topIndex+1)), and update the max area. To avoid to make the monostack empty or left elements after the loop, we add 0s to the front and the back of the input array.

Complexity

• Time complexity: $O(n)$

• Space complexity: $O(n)$

Code

func largestRectangleArea(heights []int) int {
	ans, monoStack := 0, make([]int, 0, len(heights)) // stores indices
	heights = append(append([]int{0}, heights...), 0)
	for i := 0; i < len(heights); i++ {
		for len(monoStack) > 0 && heights[i] < heights[monoStack[len(monoStack)-1]] {
			curHeight := heights[monoStack[len(monoStack)-1]]
			monoStack = monoStack[:len(monoStack)-1]
			width := i - monoStack[len(monoStack)-1] - 1
			if s := width * curHeight; s > ans {
				ans = s
			}
		}
		monoStack = append(monoStack, i)
	}
	return ans
}

Reference

1. 动画演示 单调栈 84.柱状图中最大的矩形