最大矩形

题目

思路

自己的思路

首先我们先对题目进行解读：题目要求很简单，就是给定一个二维矩阵，求出该矩阵中只包含1的最大的矩形面积，那么我们该从哪方面入手呢

• 一开始我的思路就是设置两个栈：

stack<int> start;
stack<int> end;

• 这两个栈的目的是做什么呢？我起初的思路就是求出每一行连续1的最大起始位置，start栈用来保存该行最大连续1的头位置，end栈用来保存最大连续1的结束位置，这样求出每一行各自连续1的最大起初位置之后，通过这两个栈判断出该矩阵最大包含1的最大矩形面积。拿示例来说，首先第一行最大连续的1的起始位置是（0，0），那么即把位置0压入栈start中，把0压入栈end中；第二行最大连续1的起始位置就是（2，4），同样的把2压入栈start中，把4压入栈end中，依次类推。
• 依次求出每行最大连续1的起始位置后，那我们就通过这两个栈start和end来求出结果。我的设想是这样的：相邻两行的起始位置所构成的只包含1的最大矩形面积是这样求出的，头位置取大的那个，位置取小的那个，举个例子来说，比如第一行和第二行所构成的只包含1的最大矩形面积是这样的：因为第一行最大连续1的起始位置分别是（0，0），（0，2），那么第二行最大连续1的起始位置是（2，4），那么（0，0）和（2，4）按照我们所设定的规则，取得得结果就是（2，0），这个结果头位置大于末位置，所以不能构成最大矩形；接着我们再看（0，2）和（2，4），按照所设定得规则，所得结果为（2，2），所以第一行和第二行所构成得最大矩形面积的起始位置就是（2，2）
• 依次将每一行这样子合并类推

存在的问题

这样的思路存在许多的漏洞：

1. 首先如果一行存在几个相等的最大连续1，我们都需要将他们保存下来（因为我们不知道哪个能构成最大矩形面积），我们所设定的栈就只是从每一行有且只有一个最大连续1来考虑的
2. 当连续几行所构成的最大矩形面积如果比某一行最大连续1小的话，那我们下一步又该如何进行比较呢，这个问题也不能很好的解决
3. 该思路实现起来比较困难，编程方面难度较大，而且思路也不算正确

参考思路

首先回忆一下我们再求图形中的最大矩形面积中利用到了单调栈，那么这个二维矩阵是否也跟此类似呢？很显然这道题我们也可以利用单调栈解决（为什么可以这样子说呢？我们把每一列/行看坐是一个柱状的，那么这个就跟坐标中的求最大矩形面积类似了），所以思路大概是这样的：我们将每一列看作是长度为该列最大连续1的长度，然后每次添加一行时，我们就调用判断此时最大矩形面积的函数来判断此时的最大矩形面积，代码如下：

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
		if (matrix.size() < 1 || matrix[0].size() < 1)
			return 0;
		int n = matrix[0].size();
		int result = 0;
		vector<int> heights(n, 0);
		for (int i = 0; i < matrix.size(); i++) {
			for (int j = 0; j < n; j++) {
				if (matrix[i][j] == '0')
					heights[j] = 0;
				else
					heights[j] += 1;
			}
			result = max(result, largestArea(heights));
		}
		return result;
	}

		int  largestArea(vector<int> heights) {
		stack<int> s;
		int result = 0;
		int i, j;
		heights.push_back(-1);
		for (i = 0; i < heights.size(); i++) {
			while (!s.empty() && heights[i] < heights[s.top()]) {
				int h = heights[s.top()];
				s.pop();
				result = max(result, h * (s.empty() ? i : (i - s.top() - 1)));//注意：在栈不为空时底边为什么还要减1呢，因为栈顶已经弹出一个元素了，此时栈已经后移了一位
			}
			s.push(i);
		}
		return result;
	}
};

首先我们我们先看下函数largesArea：

int  largestArea(vector<int> heights) {
		stack<int> s;
		int result = 0;
		int i, j;
		heights.push_back(-1);
		for (i = 0; i < heights.size(); i++) {
			while (!s.empty() && heights[i] < heights[s.top()]) {
				int h = heights[s.top()];
				s.pop();
				result = max(result, h * (s.empty() ? i : (i - s.top() - 1)));//注意：在栈不为空时底边为什么还要减1呢，因为栈顶已经弹出一个元素了，此时栈已经后移了一位
			}
			s.push(i);
		}
		return result;
	}

这个函数就是我们之前判断柱状图中的最大矩形面积函数，重点和难点在于如何将二维矩阵中的点转换为柱状图中最大矩形面积的模型，相关代码如下：

int maximalRectangle(vector<vector<char>>& matrix) {
		if (matrix.size() < 1 || matrix[0].size() < 1)
			return 0;
		int n = matrix[0].size();
		int result = 0;
		vector<int> heights(n, 0);
		for (int i = 0; i < matrix.size(); i++) {
			for (int j = 0; j < n; j++) {
				if (matrix[i][j] == '0')
					heights[j] = 0;
				else
					heights[j] += 1;
			}
			result = max(result, largestArea(heights));
		}
		return result;
	}

其中理解的难点在于那两个for循环，这两个循环表示：首先逐行添加，然后再遍历每一列，如果该位置为1，那么长度就加1，如果该位置为0，那么该列的长度就直接置为0，然后再调用函数largestArea，判断此时柱状图模型中的最大矩形面积

总结

这道题是柱状图中的最大矩形面积的变形，难点就在于是否懂得将二维矩阵转换为柱状图模型，一开始的时候我设想直接算出每一列的最大长度，然后只调用一次largestArea函数，但是这样却不能得出正确答案，问题的原因在于我们在每次遇到0的时候都直接将长度归回0，那么我们就不能一次性的求出该列最长的长度，只能逐行添加，然后每次都调用一次largestArea函数