给定一个二维数组matrix，其中的值不是0就是1，返回全部由1组成的最大子矩形，内部有多少个1。
按行遍历二维数组，构造直方图。
单调栈，大压小。有代码。
代码用golang编写，代码如下：
package main
import "fmt"
func main() {
matrix := [][]byte{
{1, 1, 1},
{1, 0, 1},
{1, 1, 1},
{1, 1, 1}}
ret := maximalRectangle(matrix)
fmt.Println(ret)
}
func maximalRectangle(matrix [][]byte) (ans int) {
rowsLen := len(matrix)
colsLen := len(matrix[0])
height := make([]int, colsLen)
maxArea := 0
for i := 0; i < rowsLen; i++ {
for j := 0; j < colsLen; j++ {
if matrix[i][j] == 0 {
height[j] = 0
} else {
height[j]++
}
maxArea = getMax(maxArea, largestRectangleArea(height))
}
}
return maxArea
}
func largestRectangleArea(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
}
}执行结果如下：
