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

福大大架构师每日一题 · · 152 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

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
    }
}

执行结果如下:


在这里插入图片描述

左神java代码
力扣1504. 统计全 1 子矩形
评论


有疑问加站长微信联系(非本文作者)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

152 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传