Leetcode每日一题 —— 85. 最大矩形

Leetcode每日一题 —— 85. 最大矩形

发现之前做过这题，但是代码看了好一会儿才看懂。以后还是老老实实写注释吧。
大体思路是，使用数组rect[i][j][k]表示到i行为止从 (i, j) 到 (i, k) 的列最大高度。然后从当前列往左遍历j，计算面积尝试更新最大值。

看着就有很大优化空间，今天时间有些紧张，有空再优化吧。

代码

class Solution {
    public int maximalRectangle(char matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int row = matrix.length;
        int col = matrix[0].length;
        // rect[i][j][k] 表示以 (i, j) 到 (i, k) 的最大高度
        int rect = new int[row][col][col];
        int max = 0;
        int tmp = 0;
        // 初始化第0行
        for (int j = 0; j < col; j++) {
            if (matrix[0][j] == '1') {
                rect[0][j][j] = 1;
                tmp++;
                for (int k = 1; k < tmp; k++) {
                    rect[0][j - k][j] = 1;
                }
                max = Math.max(max, tmp);
            } else {
                tmp = 0;
            }
        }

        for (int i = 1; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == '1') {
                    // 设置当前列的高度
                    rect[i][j][j] = rect[i - 1][j][j] + 1;
                    max = Math.max(max, rect[i][j][j]);
                    int k = j - 1;
                    // 从当前列的左侧开始，向左扩展，如果某列到当前列有最大高度，则尝试更新最大面积
                    while (k >= 0) {
                        if (rect[i][k][j - 1] > 0) {
                            rect[i][k][j] = rect[i - 1][k][j] + 1;
                            max = Math.max(max, rect[i][k][j] * (j - k + 1));
                        } else {
                            break;
                        }
                        k--;
                    }
                }
            }
        }
        return max;
    }
}

Leetcode的这道题要求我们在给定的二维矩阵中找到最大的矩形，该矩形中的元素都是'1'。文章中给出的代码尝试通过维护一个三维数组rect[i][j][k]来记录从第i行到第i行的每一列的最大高度，然后通过遍历每一列的左侧来计算可能的矩形面积，并尝试更新最大面积。虽然文章中提到代码还有很大的优化空间，但这个方法提供了一个基本的解决思路。对于实际应用，可能需要进一步优化以提高效率。