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));

        // 计算左边连续了多少个1
        for(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;
                else
                    l[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;
    }
};