python3 解法, 执行用时: 484 ms, 内存消耗: 37.6 MB, 提交时间: 2022-12-07 17:58:45

class Solution:
    def largestSubmatrix(self, matrix: List[List[int]]) -> int:
        #同84题，85题
        R, C = len(matrix), len(matrix[0])
        heights = [[0 for _ in range(C)] for _ in range(R)]     #每一行的高度数组
        for c in range(C):
            heights[0][c] = matrix[0][c]
        for r in range(1, R):
            for c in range(C):
                if matrix[r][c] == 1:
                    heights[r][c] = heights[r-1][c] + 1
                else:
                    heights[r][c] = 0

        res = 0
        for r in range(R):
            heights[r].sort()                       #是为了贪心
            for c in range(C):
                cur_area = heights[r][c] * (C - c)  #当前的高度就是最低了。
                res = max(res, cur_area)
        return res

java 解法, 执行用时: 9 ms, 内存消耗: 67 MB, 提交时间: 2022-12-07 17:47:41

/**
 * 预处理数组，计算以这个点为结尾，上面有多少个连续的1，
 * 就是这一列以这个点为结尾的最大高度，这样就将二维问题转成一维
 * 遍历每一行，对每一行进行排序，记录矩形的最长的高度，每次更新结果
 */
class Solution {
    public int largestSubmatrix(int[][] matrix) {
        int n=matrix.length;
        int m=matrix[0].length;
        int res=0;
        for(int i=1;i<n;i++){
            for(int j=0;j<m;j++){
                if(matrix[i][j]==1){
                    //记录向上连续1的个数
                    matrix[i][j]+=matrix[i-1][j];
                }
            }
        }
        for(int i=0;i<n;i++){
            Arrays.sort(matrix[i]);
            for(int j=m-1;j>=0;j--){
                //更新矩形的最大高度
                int height=matrix[i][j];
                //更新最大面积
                res=Math.max(res,height*(m-j));
            }
        }
        return res;
    }
}