LeetCode 最大矩形_最大矩形面积leetcode

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

示例:

输入:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
输出: 6
1
2
3
4
5
6
7
8

思路分析：请先参考 LeetCode 柱状图中的最大矩形
表面上这道题和上一道题没有什么联系，就是求的内容相似，都需要求最大矩形。其实联系就在这个矩形！
上一题是在一维线性轴，本题是二维平面求解。
本题由于二维显得有些束手无策，下面将介绍如何将这个二维转换为一维问题的求解。
我们需要求一个矩形的面积，首先需要知道它的长、宽，长就是x轴方向连续的“1”，宽就是这个“长”在y轴的连续。

降维图解！

是不是和第一题有些相似了，滑稽滑稽。
但是如何快速的到这些“长”呢？
我们使用个数组保存即可，dpRow[row][col]表示matrix[row][col]为起始向右可扩展的最大长（连续的“1”的数目）

具体代码实现。（时间复杂度为O(n³)，额外的空间复杂度为O(n²)）

class Solution {
   
public:
	int maximalRectangle(vector<vector<char>>& matrix) {
   
		int maxResult = 0;//结果
		int rowSize = matrix.size();//矩阵的行数
		if (rowSize == 0){
   
			return 0;
		}
		int colSize = matrix[0].size();//矩阵的列数
		//rowDp[row][col]表示在matrix[row][col]为起始向右可扩展的1的个数，说白了就是矩阵的最大长
		vector<vector<int> > rowDp(rowSize, vector<
1
2
3
4
5
6
7
8
9
10
11
12
13