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

import "fmt"

func largestRectangleArea(heights []int) int {
maxArea, stack, height := 0, []int{}, 0
for i := 0; i <= len(heights); i++ {
if i == len(heights) {
height = 0
} else {
height = heights[i]
}
if len(stack) == 0 || height >= heights[stack[len(stack)-1]] {
stack = append(stack, i)
} else {
tmp := stack[len(stack)-1]
fmt.Printf("1. tmp = %v stack = %v\n", tmp, stack)
stack = stack[:len(stack)-1]
length := 0
if len(stack) == 0 {
length = i
} else {
length = i - 1 - stack[len(stack)-1]
fmt.Printf("2. length = %v stack = %v i = %v\n", length, stack, i)
}
maxArea = max(maxArea, heights[tmp]*length)
fmt.Printf("3. maxArea = %v heights[tmp]*length = %v\n", maxArea, heights[tmp]*length)
i--
}
}
return maxArea
}

``````

Sep 6, 2020