【力扣 063】85. 最大矩形

85. 最大矩形

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

示例 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
 

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximal-rectangle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

可以先做84 题，然后回来考虑这道题。

再想一下这个题，看下边的橙色的部分，这完全就是 84 题呀！

代码实现：

class Solution
{
public:
  int largestRectangleArea(vector heights)
  {
    heights.insert(heights.begin(), 0);
    heights.push_back(0);
    stack stk;
    int result = 0;
    for (int i = 0; i < heights.size(); i++)
    {
      while (!stk.empty() && heights[stk.top()] > heights[i])
      {
        int height = heights[stk.top()];
        stk.pop();
        int width = i - stk.top() - 1;
        result = max(result, height * width);
      }
      stk.push(i);
    }
    return result;
  }
  
  int maximalRectangle(vector> &matrix)
  {
    int m = matrix.size(), n = matrix[0].size();
    int result = 0;
    vector heights(n, 0); // 初始化单层柱状图
    for (int i = 0; i < m; i++)
    {
      for (int j = 0; j < n; j++)
      {
        if (matrix[i][j] == '1') /// 更新单层柱状图
          heights[j] += 1;
        else
          heights[j] = 0;
      }
      result = max(result, largestRectangleArea(heights)); // 送入单调栈方法获得结果
    }
    return result;
  }
};

参考资料

1. 详细通俗的思路分析，多解法