给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。

    示例 1:
    image.png

    输入:matrix = [[“1”,”0”,”1”,”0”,”0”],[“1”,”0”,”1”,”1”,”1”],[“1”,”1”,”1”,”1”,”1”],[“1”,”0”,”0”,”1”,”0”]]
    输出:6
    解释:最大矩形如上图所示。
    示例 2:

    输入:matrix = []
    输出:0
    示例 3:

    输入:matrix = [[“0”]]
    输出:0
    示例 4:

    输入:matrix = [[“1”]]
    输出:1
    示例 5:

    输入:matrix = [[“0”,”0”]]
    输出:0

    提示:

    rows == matrix.length
    cols == matrix[0].length
    1 <= row, cols <= 200
    matrix[i][j] 为 ‘0’ 或 ‘1’


    1. class Solution {
    2. /**
    3. 我们可以将此题转化为上道直方图求矩形最大面积,怎么转化?
    4. 遍历每一行,只有当当前位置是'1'时,我们才把它以前的值加上,
    5. 例如"1101","1011" 第二行我们可以转化为"2002"
    6. 然后对每一行运用单调栈求解每一行最大值,并维护答案
    7. */
    8. int[] st; //模拟栈
    9. int tt; //模拟栈顶
    10. public int maximalRectangle(char[][] matrix) {
    11. int n = matrix.length, m = n == 0 ? 0 : matrix[0].length;
    12. if (n == 0) return 0;
    13. int res = 0;
    14. st = new int[m+1];
    15. //每行多开两个是因为后面我们加入两个哨兵,因为我们维护的是单调上升栈
    16. int[][] dir = new int[n][m+2];
    17. for (int i = 0; i < n; ++i)
    18. for (int j = 1; j <= m; ++j) {
    19. dir[i][j] = matrix[i][j-1]-'0';
    20. //只有当当前值是"1"才加上之前的值
    21. if (i > 0 && matrix[i][j-1] == '1')
    22. dir[i][j] += dir[i-1][j];
    23. }
    24. //求解每一行的最大值
    25. for (int i = 0; i < n; ++i) {
    26. tt = 0;
    27. int[] c = dir[i];
    28. c[0] = 0;
    29. c[m+1] = 0;
    30. for (int j = 1; j <= m+1; ++j) {
    31. while (tt > 0 && c[st[tt]] >= c[j]) {
    32. int cur = c[st[tt--]];
    33. int l = st[tt]+1;
    34. int r = j-1;
    35. res = Math.max(res,cur*(r-l+1));
    36. }
    37. st[++tt] = j;
    38. }
    39. }
    40. return res;
    41. }
    42. }