85. 最大矩形

题目描述

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例 1：

输入：matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]]
输出：6
解释：最大矩形如上图所示。

示例 2：

输入：matrix = []
输出：0

示例 3：

输入：matrix = [[“0”]]
输出：0

示例 4：

输入：matrix = [[“1”]]
输出：1

示例 5：

输入：matrix = [[“0”,“0”]]
输出：0

提示：

rows == matrix.length
cols == matrix[0].length
1 <= row, cols <= 200
matrix[i][j] 为 '0' 或 '1'

解法一：单调栈 + 动态规划

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


func max(nums ...int) int {
    res := nums[0]
    for _, val := range nums {
        if val > res {
            res = val
        }
    }
    return res
}
func maximalRectangle(matrix [][]byte) int {
    h, w := len(matrix), len(matrix[0])
    // 构造 h+1 行的矩阵，最后一行的值全为 0
    left := make([][]int, h+1)
    for i := 0; i <= h; i++ {
        left[i] = make([]int, w)
    }
    for i := 0; i < h; i++ {
        for j := 0; j < w; j++ {
            if j > 0 {
                left[i][j] = left[i][j-1]
            }
            if matrix[i][j] == '0' {
                left[i][j] = 0
            } else {
                left[i][j] += 1
            }
        }
    }
    ans := 0
    for j := 0; j < w; j++ {
        var stack []int
        stack = append(stack, -1)
        for i := 0; i <= h; i++ {
            // left[stack[len(stack)-1]][j] >= left[i][j] 可以换成
            // left[stack[len(stack)-1]][j] > left[i][j]
            for stack[len(stack)-1] != -1 && left[stack[len(stack)-1]][j] >= left[i][j] {
                h := left[stack[len(stack)-1]][j]
                stack = stack[:len(stack)-1]
                l := stack[len(stack)-1]
                w := i - l - 1
                ans = max(ans, w*h)
            }
            stack = append(stack, i)
        }
    }
    return ans
}