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 } }
执行结果如下: