2020-03-01：给定一个非负数组arr，代表直方图。返回直方图的最大长方形面积。

福大大架构师每日一题 · · 387 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

2020-03-01：给定一个非负数组arr，代表直方图。返回直方图的最大长方形面积。
福哥答案2020-03-01：

单调栈，大压小。有代码。

代码用golang编写，代码如下：

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

执行结果如下：