2021-03-20：给定一个二维数组matrix，其中的值不是0就是1，返回全部由1组成的子矩形数量。

福大大架构师每日一题 · · 336 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

福大大答案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
    }
}

执行结果如下：