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

執行結果如下：

評論