LeetCode 85. 最大矩形

预备知识

84.柱状图中最大的矩形：题目链接

思路：在求柱状图最大面积时，我们可以枚举每一根柱子，并且假设这根柱子就是最大面积中最低的那一根柱子。由于最大面积的选中的柱子中，矩形的高取决于最低的柱子，现在已知矩形的高，知道矩形的宽即可求出最大矩形面积。矩形的宽如何求呢？如果我们对每一根柱子A，可以知道在左边第一个低于他的柱子是B，在右边第一个低于他的柱子是C，那么这两根柱子之间的柱子一定都高于等于柱子A，矩形的宽就为C-B-1。

我们可以开一个栈（存柱子的编号），并维护从栈顶到栈底，柱子高度是从高到低的，在遍历时会有以下几种情况：

1. 当前柱子a 低于栈顶柱子b，那么可以得知柱子b右边第一个比他低的柱子就是a
2. 当前柱子a 高于栈顶柱子b，那么可以得知：柱子b左边第一个比他低的柱子就是a
3. 栈为空，说明左边没有比他低的柱子。

class Solution {
public:int largestRectangleArea(vector<int>& heights) {int n = heights.size();vector<int> l(n), r(n);stack<int>stk;int ans = 0;for(int i=0;i<n;i++){while(!stk.empty() && heights[i] < heights[stk.top()]){r[stk.top()] = i;stk.pop();}if(stk.empty()) l[i] = -1;else l[i] = stk.top();stk.push(i);}while(!stk.empty()){r[stk.top()] = n;stk.pop();}for(int i=0;i<n;i++){ans = max(ans,heights[i]*(r[i]-l[i]-1));}return ans;}
};

思路

想法1：按照上面的思路，枚举每一列，然后求得左边连续的长度和右边连续的长度，以这条边作为矩形的宽计算。但这种方法并不行，因为左右不一定都取最长，因为在一边取最长的前提下，另一边也取最长可能会影响矩形的高度，反而使矩形达不到最大。

思路：其实只需要求得左边连续的长度即可，换一种角度想，我枚举每一列时，其实是在枚举最大矩阵的优边界，那么即使我只计算了这一列左半部分的矩阵面积，右半部分的面积没有计算，显然不是最大矩阵。但是我可以在枚举下一列时，得到更大的面积，直到枚举到最大矩阵右边界的那一列，可以得到最大面积，这个最大面积就是右边界那一列左半部分的面积，无需再向右延伸。

class Solution {
public:int maximalRectangle(vector<vector<char>>& matrix) {int n = matrix.size();int m = matrix[0].size();int ans = 0;vector<vector<int>> l(n,vector<int>(m,0));// 计算左边连续了多少个1for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(matrix[i][j] == '1')l[i][j] = j ? l[i][j-1] + 1 : 1;elsel[i][j] = 0;stack<int> stk;vector<int> up(n), down(n);for(int j=0;j<m;j++){for(int i=0;i<n;i++){while(!stk.empty() && l[i][j] < l[stk.top()][j])down[stk.top()] = i , stk.pop();if(!stk.empty()) up[i] = stk.top();else up[i] = -1;stk.push(i);}while(!stk.empty()){down[stk.top()] = n;stk.pop();}for(int i=0;i<n;i++)ans = max(ans, l[i][j]*(down[i]-up[i]-1));}return ans;}
};