2020-03-01：給定一個非負陣列arr，代表直方圖。返回直方圖的最大長方形面積。

福哥答案2020-03-01：

單調棧，大壓小。有程式碼。

程式碼用golang編寫，程式碼如下：

```go

package main

import (

"container/list"

"fmt"

)

func main() {

arr := []int{3, 2, 4, 2, 5}

fmt.Println(largestRectangleArea1(arr))

fmt.Println(largestRectangleArea2(arr))

}

func largestRectangleArea1(height []int) int {

if len(height) == 0 {

return 0

}

maxArea := 0

stack := list.New().Init()

N := len(height)

for i := 0; i < N; i++ {

for !(stack.Len() == 0) && height[i] <= height[stack.Back().Value.(int)] {

j := stack.Back().Value.(int)

stack.Remove(stack.Back())

k := 0

if stack.Len() == 0 {

k = -1

} else {

k = stack.Back().Value.(int)

}

curArea := (i - k - 1) * height[j]

maxArea = getMax(maxArea, curArea)

}

stack.PushBack(i)

}

for !(stack.Len() == 0) {

j := stack.Back().Value.(int)

stack.Remove(stack.Back())

k := 0

if stack.Len() == 0 {

k = -1

} else {

k = stack.Back().Value.(int)

}

curArea := (N - k - 1) * height[j]

maxArea = getMax(maxArea, curArea)

}

return maxArea

}

func largestRectangleArea2(height []int) int {

if len(height) == 0 {

return 0

}

N := len(height)

stack := make([]int, N)

si := -1

maxArea := 0

for i := 0; i < N; i++ {

for si != -1 && height[i] <= height[stack[si]] {

j := stack[si]

si--

k := 0

if si == -1 {

k = -1

} else {

k = stack[si]

}

curArea := (i - k - 1) * height[j]

maxArea = getMax(maxArea, curArea)

}

si++

stack[si] = i

}

for si != -1 {

j := stack[si]

si--

k := 0

if si == -1 {

k = -1

} else {

k = stack[si]

}

curArea := (N - k - 1) * height[j]

maxArea = getMax(maxArea, curArea)

}

return maxArea

}

func getMax(a int, b int) int {

if a > b {

return a

} else {

return b

}

}

```

執行結果如下：

***

[左神java程式碼](https://github.com/algorithmzuo/algorithmbasic2020/blob/master/src/class25/Code03_LargestRectangleInHistogram.java)

[力扣84. 柱狀圖中最大的矩形](https://leetcode-cn.com/problems/largest-rectangle-in-histogram/)