2021-03-19:给定一个二维数组matrix,其中的值不是0就是1,返回全部由1组成的最大子矩形,内部有多少个1。

2021-03-19:给定一个二维数组matrix,其中的值不是0就是1,返回全部由1组成的最大子矩形,内部有多少个1。

福大大 答案2021-03-19:

按行遍历二维数组,构造直方图。
单调栈,大压小。有代码。

代码用golang编写,代码如下:

package main

import "fmt"

func main() {
    matrix := [][]byte{
        {1, 1, 1},
        {1, 0, 1},
        {1, 1, 1},
        {1, 1, 1}}
    ret := maximalRectangle(matrix)
    fmt.Println(ret)
}
func maximalRectangle(matrix [][]byte) (ans int) {
    rowsLen := len(matrix)
    colsLen := len(matrix[0])
    height := make([]int, colsLen)
    maxArea := 0
    for i := 0; i < rowsLen; i++ {
        for j := 0; j < colsLen; j++ {
            if matrix[i][j] == 0 {
                height[j] = 0
            } else {
                height[j]++
            }
            maxArea = getMax(maxArea, largestRectangleArea(height))
        }
    }
    return maxArea
}

func largestRectangleArea(height []int) int {
    if len(height) == 0 {
        return 0
    }
    N := len(height)
    stack := make([]int, N)
    si := -1
    maxArea := 0
    for i := 0; i < N; i++ {
        for si != -1 && height[i] <= height[stack[si]] {
            j := stack[si]
            si--
            k := 0
            if si == -1 {
                k = -1
            } else {
                k = stack[si]
            }
            curArea := (i - k - 1) * height[j]
            maxArea = getMax(maxArea, curArea)
        }
        si++
        stack[si] = i
    }
    for si != -1 {
        j := stack[si]
        si--
        k := 0
        if si == -1 {
            k = -1
        } else {
            k = stack[si]
        }
        curArea := (N - k - 1) * height[j]
        maxArea = getMax(maxArea, curArea)
    }
    return maxArea
}
func getMax(a int, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}

执行结果如下:
在这里插入图片描述


评论

福大大架构师每日一题 文章被收录于专栏

最新面试题,针对高级开发人员和架构师。内容是后端、大数据和人工智能。

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
点赞 评论 收藏
转发
3 收藏 评论
分享

全站热榜

正在热议