2021-03-20：给定一个二维数组matrix，其中的值不是0就是1，返回全部由1组成的子矩形数量。
福大大 答案2021-03-20：
按行遍历二维数组，构造直方图。
单调栈，大压小。有代码。
代码用golang编写，代码如下：
package main
import "fmt"
func main() {
matrix := [][]int{
{1, 1, 1, 1, 1, 1},
}
ret := numSubmat(matrix)
fmt.Println(ret)
}
func numSubmat(mat [][]int) int {
if len(mat) == 0 || len(mat[0]) == 0 {
return 0
}
nums := 0
height := make([]int, len(mat[0]))
for i := 0; i < len(mat); i++ {
for j := 0; j < len(mat[0]); j++ {
if mat[i][j] == 0 {
height[j] = 0
} else {
height[j]++
}
}
nums += countFromBottom(height)
}
return nums
}
func countFromBottom(height []int) int {
if len(height) == 0 {
return 0
}
nums := 0
stack := make([]int, len(height))
si := -1
for i := 0; i < len(height); i++ {
for si != -1 && height[stack[si]] >= height[i] {
cur := stack[si]
si--
if height[cur] > height[i] {
left := -1
if si != -1 {
left = stack[si]
}
n := i - left - 1
heightleft := 0
if left != -1 {
heightleft = height[left]
}
down := getMax(heightleft, height[i])
nums += (height[cur] - down) * num(n)
}
}
si++
stack[si] = i
}
for si != -1 {
cur := stack[si]
si--
left := -1
if si != -1 {
left = stack[si]
}
n := len(height) - left - 1
down := 0
if left != -1 {
down = height[left]
}
nums += (height[cur] - down) * num(n)
}
return nums
}
func num(n int) int {
return (n * (1 + n)) >> 1
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}
执行结果如下：
在这里插入图片描述
