2021-03-20：给定一个二维数组matrix，其中的值不是0就是1，返回全部由1组成的子矩形数量。
福大大 答案2021-03-20：
按行遍历二维数组，构造直方图。
单调栈，大压小。有代码。
代码用golang编写，代码如下：
package mainimport "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 }}执行结果如下：
左神java代码
力扣1504. 统计全 1 子矩形
评论