原题传送门

1. 题目描述

2. Solution 1

1、思路分析
以 example 1. 为例
matrix = [
[1,0,1,0,0],
[1,0,1,1,1],
[1,1,1,1,1],
[1,0,0,1,0]
]

分析: 遍历 行(row)
row = 1: 可以得到 heights = [1, 0, 1, 0, 0] 套用 Q84
row = 2: -> heights = [2, 0, 2, 1, 1]
......

2、代码实现

package Q0099.Q0085MaximalRectangle;  import java.util.ArrayDeque; import java.util.Deque;  /*    以 example 1. 为例     matrix = [       [1,0,1,0,0],       [1,0,1,1,1],       [1,1,1,1,1],       [1,0,0,1,0]     ]      分析: 遍历 行(row)     row = 1: 可以得到 heights = [1, 0, 1, 0, 0] 套用 Q84     row = 2: -> heights = [2, 0, 2, 1, 1]     ......   */ public class Solution1 {     public int maximalRectangle(char[][] matrix) {         if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;         int col = matrix[0].length;         int[] heights = new int[col];         int max = 0;         for (char[] chars : matrix) {             for (int j = 0; j < col; j++) {                 if (chars[j] == '1') {                     heights[j]++;                 } else {                     heights[j] = 0;                 }             }             int area = largestRectangleArea(heights);             max = Math.max(max, area);         }         return max;     }      // 来自 Q84     public int largestRectangleArea(int[] heights) {         int len = heights.length;         Deque<Integer> s = new ArrayDeque<>();         int maxArea = 0;         for (int i = 0; i <= len; i++) {             int h = (i == len ? 0 : heights[i]);             if (s.isEmpty() || h >= heights[s.peek()]) {                 s.push(i);             } else {                 int tp = s.pop();                 int width = (s.isEmpty() ? i : i - 1 - s.peek());                 maxArea = Math.max(maxArea, heights[tp] * width);                 i--;             }         }         return maxArea;     } } 

3、复杂度分析
时间复杂度: O(m * n) 其中 dim(matrix) = (m, n)
空间复杂度: O(n) 栈

2. Solution 2

1、思路分析
思路同Solution 1，用数组模拟栈。
2、代码实现

package Q0099.Q0085MaximalRectangle;  public class Solution2 {     /*     执行耗时:2 ms,击败了100.00% 的Java用户     内存消耗:41.8 MB,击败了36.24% 的Java用户     */     //方案2     public int maximalRectangle(char[][] matrix) {         if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;         int m = matrix.length;         int n = matrix[0].length;         int[] dp = new int[n + 1];//增加一列，简化边界处理         int res = 0;         for (int row = 0; row < m; row++) {             updateHeight(dp, row, matrix);              res = Math.max(res, maxArea(dp));         }         return res;     }      public void updateHeight(int[] dp, int row, char[][] matrix) {         for (int column = 0; column < matrix[row].length; column++) {             dp[column] = matrix[row][column] == '1' ? dp[column] + 1 : 0;         }     }      public int maxArea(int[] heights) {         int l = 0, r = 0;         int n = heights.length;         int[] pos = new int[n + 1];         pos[l] = -1;         int res = 0;         while (r < n) {             while (l > 0 && heights[r] < heights[pos[l]]) {                 int h = heights[pos[l--]];                 res = Math.max(res, h * (r - pos[l] - 1));             }             pos[++l] = r++;         }         return res;     } }  

3、复杂度分析
时间复杂度: O(m * n) 其中 dim(matrix) = (m, n)
空间复杂度: O(n) 栈