题目分析

本题有一定的难度，但是难度不是很大，没有思路的小伙伴，给一些提示，参考柱状图中最大的矩形的解法，然后试着写出本题。

动态规划+单调栈

Leetcode84题是本题的一部分，本题的题意可以转化为，先找到每一行的高度，然后求柱状图中最大的矩形。每一行的高度可以使用DP来求解，用dp[i][j]表示第i行第j列的高度(列方向有多少连续个1)。

$$ dp[i][j] = \begin{cases} dp[i - 1][j] + 1 & mat[i][j] = ‘1’ \ 0 & mat[i][j] = ‘0’ \end{cases} $$

因为每次更新dp数组时j不会变，因此可以使用一维DP代替二维。

$$ dp[i] = \begin{cases} dp[i - 1] + 1 & mat[i][j] = ‘1’ \ 0 & mat[i][j] = ‘0’ \end{cases} $$

求解出每一行的高度时，直接调用第84题的算法即可求得以该行为底边的最大矩形，遍历所有的行求出最大值即可。

算法的**时间复杂度为O(mn)，空间复杂度为O(n)**，其中m为矩阵行数、n为矩阵列数。

本题使用84题的暴力算法也可以通过，因为84题暴力算法的**时间复杂度为O(n^2)，空间复杂度为O(n)，本题再多遍历一个行数m，因此本题暴力算法的时间复杂度为O(mn^2)，空间复杂度为O(n)**，其中m为矩阵行数、n为矩阵列数。

这里就不给出暴力算法的代码了，直接看柱状图中最大的矩形即可。

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int row = matrix.length;
        if (row == 0) {
            return 0;
        }
        int col = matrix[0].length;
        int res = 0;
        int[] height = new int[col];
        for (char[] chars : matrix) {
            for (int j = 0; j < col; j++) {
                height[j] = chars[j] == '1' ? height[j] + 1 : 0;
            }
            res = Math.max(res, largestRectangleArea(height));
        }
        return res;
    }

    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] newHeights = new int[n + 2];
        System.arraycopy(heights, 0, newHeights, 1, n);
        LinkedList<Integer> list = new LinkedList<>();
        int res = 0;
        for (int i = 0; i < n + 2; i++) {
            while (!list.isEmpty() && newHeights[i] < newHeights[list.getLast()]) {
                int idx = list.pollLast();
                if (!list.isEmpty()) {
                    res = Math.max(res, newHeights[idx] * (i - list.getLast() - 1));
                }
            }
            list.add(i);
        }
        return res;
    }
}

刷题总结

题目难度不大，主要是看小伙伴能否从二维矩阵中抽象出柱状图中最大的矩形，这一点是有难度的。