一、题目

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

点击查看原题
难度级别：困难

二、思路

1）记录竖向连续1数量

定义一个数组cnt[col]，代表遍历到当前matrix中row行col列，matrix中从当前位置竖直向上计数，连续为‘1’的计数。
当且仅当cnt从i到j（j<=i）不存在0时，构成矩形，记录下cnt[i，j]的最小值minHigh，则矩形的面积为minHigh*(i-j+1)

三、代码

1）记录竖向连续1数量

  1. class Solution {
  2.     public int maximalRectangle(char[][] matrix) {
  3.         if (matrix == null || matrix.length == 0) {
  4.             return 0;
  5.         }
  6.         int[] cnt = new int[matrix[0].length];
  7.         int ans = 0;
  8.         for (int row = 0; row < matrix.length; row++) {
  9.             for (int col = 0; col < matrix[0].length; col++) {
  10.                 if (matrix[row][col] == '1') {
  11.                     cnt[col]++;
  12.                     int minHigh = cnt[col];
  13.                     for (int i = col; i >= 0 && cnt[i] != 0; i--) {
  14.                         minHigh = Math.min(minHigh, cnt[i]);
  15.                         ans = Math.max(ans, minHigh * (col - i + 1));
  16.                     }
  17.                 } else {
  18.                     cnt[col] = 0;
  19.                 }
  20.             }
  21.         }
  22.         return ans;
  23.     }
  24. }

时间复杂度为O(m*n*n)，空间复杂度为O(n)