> For the complete documentation index, see [llms.txt](https://txfs19260817.gitbook.io/leetcode-go-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://txfs19260817.gitbook.io/leetcode-go-notes/solutions/84.-largest-rectangle-in-histogram.md).

# 84. Largest Rectangle in Histogram

## LeetCode [84. Largest Rectangle in Histogram](https://github.com/txfs19260817/LeetCode-Go/blob/master/solutions/title/README.md)

### 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:**

![](https://assets.leetcode.com/uploads/2021/01/04/histogram.jpg)

```
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:**

![](https://assets.leetcode.com/uploads/2021/01/04/histogram-1.jpg)

```
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

```go
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.柱状图中最大的矩形](https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/dong-hua-yan-shi-dan-diao-zhan-84zhu-zhu-03w3/)