leetcode85：Maximal Rectangle-蒲公英云

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

Example:

Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

求01矩阵中最大的子矩阵，这个子矩阵中全部是1.

题意还是比较简单的，感觉比较有意思，就自己做了一下。

方法1 O(n^4)：

开始考虑的是利用二维前缀和（sum[i][j]代表从左上角是0,0 右下角是i,j组成的矩形中的1的个数），这样再分别枚举矩形的左上角和右下角，当左上角和右下角组成的矩形的前缀和和等于其坐标面积时，表明这个矩形里面全部是1，不断更新答案，最后肯定能算出最大的矩形面积。假设左上角的坐标x,y，右下角的坐标i,j，那么其组成的矩形前缀和计算可以用sum[i][j] - sum[x-1][y] - sum[x][y-1] + sum[x-1][y-1]表示。这里因为要枚举两个点，每个点要两个参数确定，因此复杂度是O(n^4)，明显不像是最优解。

方法2 O(n^3):

后面想到以前做过二维矩阵中求和最大的子矩阵，跟这题类似。我们可以将矩阵中的1视为1，但是0要视为比较小的值，比如-1e8。这样的话用最大和子矩阵来求解，最终的结果中肯定不会包含0点，因为包含的话会导致总和急剧减少。我们可以利用这种方法来将其转换成最大子矩阵的问题。

最大子矩阵：一维的连续最大和比较简单，在遍历数组时，累计前缀和sum，当sum小于0时，我们完全可以丢弃前面的部分，将sum变为0，当sum大于0时，我们更新答案。这样一维连续最大和的复杂度是O(N)。到二维情况，我们可以将每一列压缩，每一列计算前缀和，当需要第i行和第k行之间的所有列的压缩值时，可以利用之前计算的前缀和计算：sum[k][j] - sum[i-1][j]。最后我们枚举行，开始i结束k，对于每个i和k，都用一维计算最大连续和的方法，此时列已经被压缩，计算的最大连续和其实也就是二维中的最大子矩阵。

方法3：O(n^2):

之前已经学会求直方图中的最大矩形（链接），现在可以将这个问题利用列的前缀和计算一下，就变成了一样的问题，不过我们需要在每一行上都计算一次，因为每列上的直方图不是从统一的一行开始的。

将每一列计算前缀和，然后在每一行上，进行一次复杂度是O(n)的直方图中最大矩阵的计算。这样总的复杂度是O(N^2)。

方法2代码：O(n^3)

//方法2：O(n^3)
func maximalRectangle(matrix [][]byte) int {
    var n int
    if n = len(matrix); n == 0 {
        return 0
    }
    m := len(matrix[0])
    // var sum [][]int
    // for i:=0; i<n; i++ {
    //     m := len(matrix[i])
    //     tmp := make([]int, m)
    //     add := 0
    //     for j:=m-1; j>=0 ; j-- {
    //         if string(matrix[i][j]) == "1" {  //todo
    //             add += 1
    //         } else {
    //             add = 0
    //         }
    //         tmp[j] = add
    //     }
    //     sum = append(sum, tmp)
    // }
    var sum[][]int
    for i := 0; i < n; i++ {
        tmp := make([]int, m)
        sum = append(sum, tmp)
    }
    for j := 0; j < m; j++ {
        add := 0
        for i := 0; i < n; i++ {
            if matrix[i][j] == '1' {
                add += 1
            } else {
                add -= 1000000
            }
            sum[i][j] = add
        }
    }
    ans := 0
    for i := 0; i < n; i++ {
        for j := i; j < n; j++ {
            updateAnswer(sum, i, j, m, &ans)
        }
    }
    return ans
}
func updateAnswer(sum [][]int, start, end, m int, ans *int) {
    ret := 0
    for j := 0; j < m; j++ {
        nowValue := 0
        if start == 0 {
            nowValue = sum[end][j]
        } else {
            nowValue = sum[end][j] - sum[start - 1][j]
        }
        ret += nowValue
        if ret > *ans {
            *ans = ret
        } else if ret < 0 {
            ret = 0
        }
    }
}

方法3代码：O(n^2)

//方法3：O(n^2)
func maximalRectangle(matrix [][]byte) int {
    var n int
    if n = len(matrix); n == 0 {
        return 0
    }
    m := len(matrix[0])
    var sum[][]int
    for i := 0; i < n; i++ {
        tmp := make([]int, m)
        sum = append(sum, tmp)
    }
    for j := 0; j < m; j++ {
        add := 0
        for i := 0; i < n; i++ {
            if matrix[i][j] == '1' {
                add += 1
            } else {
                add = 0
            }
            sum[i][j] = add
        }
    }
    ans := 0
    for i := 0; i < n; i++ {
        calMaxRectangle(sum[i], m, &ans)
    }
    return ans
}
func calMaxRectangle(sum []int, m int, ans *int) {
    s := make([]int, m)
    for j := 0; j < m; j++ {
        if len(s) == 0 || sum[j] >= sum[s[len(s) - 1]] {
            s = append(s, j)
            continue
        }
        for {
            height := sum[s[len(s) - 1]]
            s = s[:len(s) - 1]
            if len(s) == 0 {
                if *ans < height * j {
                    *ans = height * j
                    fmt.Printf("height == %v, j == %v\n", height, j)
                }
                break
            }
            width := j - s[len(s) - 1] - 1
            if height * width > *ans {
                *ans = height * width
            }
            if sum[s[len(s) - 1]] <= sum[j] {
                break
            }
        }
        j--
    }
    fmt.Println("here")
    for {
        height := sum[s[len(s) - 1]]
        s = s[:len(s) - 1]
        if len(s) == 0 { //最后一个元素出栈
            if *ans < height * m {
                *ans = height * m
                fmt.Printf("height == %v, m == %v\n", height, m)
            }
            break
        }
        width := m - s[len(s) - 1] - 1
        if height * width > *ans {
            *ans = height * width
        }
    }
    fmt.Printf("ans == %v\n", *ans)
}