力扣85-最大矩形

一、原题题目

1.1 题目

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

1.2 示例

示例1：

输入： 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

提示：

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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/maximal-rectangle/

二、解题思路

解题思路

这个题基于力扣第84题-柱状图中最大的矩形可以比较容易的想到思路，我们可以一行一行的考虑最大的矩形，如图所示。利用上一题的思路还是很容易想到解题思路的。

详细代码（Java）

public int maximalRectangle(char[][] matrix) {
    if(matrix.length == 0|| matrix == null) return 0;   // 当字符二维数组不存在输出0
    int[] a = new int[matrix[0].length];        // 记录每一行中每一个位置向上连续1的个数
    int max = 0;        // 记录最大的矩形面积，初始化为0
    for (int i = 0;i<matrix.length;i++){        // 遍历每一行
      for (int j = 0;j<matrix[0].length;j++){ // 统计每一个位置向上连续1的个数
        int count = 0;      // 每一个位置初始化向上连续1的个数为0
        for (int k = i;k>=0;k--){   // 向上遍历
          if (matrix[k][j]=='1')count++;
          else break;
        }
        a[j] = count;
      }
      max = Math.max(max,largestRectangleArea(a));
    }
    return max;
}
// 第84题-柱状图中最大的矩形
public int largestRectangleArea(int[] heights) {
    if (heights == null || heights.length==0)   return 0;   // 数组为空返回0
    int len = heights.length;       // 记录长度
    int Smax = 0;                   // 记录最大面积
    Deque<Integer> stack = new ArrayDeque<>(len);
    for (int i =0;i<len;i++){       // 遍历每一个元素
      // 栈不为空，且当前元素小于栈顶元素，则计算栈顶元素能勾勒矩形的面积
      while (!stack.isEmpty()&&heights[i]<heights[stack.peekLast()]){
        int right = i;          // 右边界为当前下标
        int height = heights[stack.pollLast()]; // 栈顶出栈记录高度
        int left = stack.isEmpty()?-1:stack.peekLast();  // 左边界：栈不空则为栈顶元素，否则为-1
        Smax = Math.max(Smax,height*(right-left-1));    // 计算面积比较
      }
      stack.addLast(i);   // 栈顶元素不大于当前值，入栈
    }
    while (!stack.isEmpty()){   // 遍历完了数组
      int right = len;        // 右边界为数组长度
      int height = heights[stack.pollLast()]; // 栈顶出栈记录高度
      int left = stack.isEmpty()?-1:stack.peekLast(); // 左边界：栈不空则为栈顶元素，否则为-1
      Smax = Math.max(Smax,height*(right-left-1));    // 计算面积比较
    }
    return Smax;
}