关于福大大架构师每日一题:20200301给定一个非负数组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. 柱状图中最大的矩形
评论