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

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

    }

}

执行结果如下：

---

左神java代码

力扣84. 柱状图中最大的矩形

评论

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