题目分析

Leetcode的题目都是类似的，做的多了都能够从以前做的题目中发现相似之处，本题和Leetcode84类似，遇到最大矩形面积的问题，通常都要使用数组height[i][j]计算(i, j)上方的最大高度，那么就提示那么多吧，小伙伴们根据提示思考下一步如何解决？

数学

这个问题的解法比较固定，不属于贪心、搜索、二分、动态规划等类别，因此放在数学的领域之中。因为本题的列是可以任意排列的，而且(i, j)上方的最大高度已知，如某一行的最大高度为[5, 2, 4, 0, 7, 3]说明子矩阵的排布是满足下图关系的。

因为矩阵的最大面积取决于最短的列，因此可以通过排序计算矩阵的最大面积。设当前行排序后的高度为height[col]，其中列数为col，排序后从最高的列开始遍历，因为最高的列宽度为1，那么最大面积为height[col - 1] x 1，倒数第二高的列右边的宽度都大于等于该列，因此宽度为2。认真思考的小伙伴就会有疑问，如果倒数第三列和倒数第二列相等，宽度不就是3了吗？不要着急，因为这种情况会在下一次遍历到，所以也会考虑到这种情况的。

算法的**时间复杂度为$O(nm)$，空间复杂度为$O(m)$**。

下面是Java语言的题解

class Solution {
    public int largestSubmatrix(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        int[] height = new int[col];
        int res = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                height[j] = matrix[i][j] == 1 ? height[j] + 1 : 0;
            }
            int[] sortHeight = height.clone();
            Arrays.sort(sortHeight);
            for (int j = col - 1; j >= 0; j--) {
                if (sortHeight[j] * col <= res) {
                    break;
                }
                res = Math.max(res, sortHeight[j] * (col - j));
            }
        }
        return res;
    }
}

刷题总结

遇到子矩阵面积的问题，一定要从高度入手，一般这种题目的时间复杂度都会卡的很准，让暴力法无法通过，因此一定不要使用暴力法进行解答。