1
2
3

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

1
2

输入：matrix = []
输出：0

1
2

输入：matrix = [["0"]]
输出：0

1
2

输入：matrix = [["1"]]
输出：1

1
2

输入：matrix = [["0","0"]]
输出：0

 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

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 动态规划
    /// 1. 令 heights[i][j]: matrix[i][j]从上到下连续'1'的个数(高度);
    /// 2. 如果 matrix[i][j] == '0', => heights[i][j] = 0;
    ///        matrix[i][j] == '1', => heights[i][j] = heights[i-1][j] + 1;
    /// 3. 令 dp[i][j][k]: 表示以matrix[i][j]为右下角的,高度为k的最大矩形面积;
    ///    则 matrix[i][j] == '0' => dp[i][j][k] = 0;
    ///       matrix[i][j] == '1' => dp[i][j][k] = dp[i][j-1][k] + k;
    pub fn maximal_rectangle(matrix: Vec<Vec<char>>) -> i32 {
        let (m, n) = (matrix.len(), matrix[0].len());
        let mut heights = vec![vec![0; n + 1]; m + 1]; // matrix[i][j]从上到下连续1的个数
        let mut dp = vec![vec![vec![0_i32; m + 1]; n + 1]; m + 1]; //

        let mut res = 0;
        for i in 0..m {
            for j in 0..n {
                if matrix[i][j] == '0' {
                    continue;
                }
                heights[i + 1][j + 1] = heights[i][j + 1] + 1;
                for k in 1..=heights[i + 1][j + 1] {
                    dp[i + 1][j + 1][k] = dp[i + 1][j][k] + (k as i32);
                    res = res.max(dp[i + 1][j + 1][k]);
                }
            }
        }

        res
    }
}
// @lc code=end

struct Solution;