2020-03-01：给定一个非负数组arr，代表直方图。返回直方图的最大长方形面积。
16lz
2021-03-02
2020-03-01：给定一个非负数组arr，代表直方图。返回直方图的最大长方形面积。
福哥答案2020-03-01：
单调栈，大压小。有代码。
代码用golang编写，代码如下：
package mainimport ( "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. 柱状图中最大的矩形
评论
你的鼓励让我更有动力
赞赏
0人进行了赞赏支持
更多相关文章
- 我的第32个代码
- MySQL的Bugs
- springboot2.x引入Mybatis-plus-generator代码自动生成工具
- 最近两年都跑哪去了，三句话告诉你
- 【asp.net core 系列】9 实战之 UnitOfWork以及自定义代码生成
- 我的第31个代码
- 我的第30个代码
- 经典面试题(18)：以下代码将输出的结果是什么？
- 经典面试题(19)：以下代码将输出的结果是什么？