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. 柱状图中最大的矩形
评论