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