0084. Largest Rectangle in Histogram

# 84. Largest Rectangle in Histogram#

## 题目 #

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

``````

## 代码 #

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

``````

Apr 8, 2023