本页目录

LeetCode 85.最大矩形

0 views · 2024-07-02

原题链接：最大矩形

本题思路基于柱状图中最大的矩形。考虑样例：

Plain Text
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

我们求出数组heights_of_line，heights_of_line[i]代表以第i行为底的柱状图heights数组。对于上述样例，heights_of_line为：

Plain Text
1 0 1 0 0
2 0 2 1 1
3 1 3 2 2
4 0 0 3 0

对于每一行，我们都可以求出最大矩形面积，最后统计最大值即可。这里的largestRectangleArea函数就是柱状图中最大的矩形的解。

C++
#define N 205
class Solution {
public:
    //求arr中元素左边第一个更小元素的下标，保存到left
    void getLeft(vector<int> &arr,vector<int> &left)
    {
        int n=arr.size();
        int st[N],top=-1;
        for(int i=0;i<n;i++)
        {
            while(top>=0&&arr[st[top]]>arr[i])
            {
                top--;
            }
            if(top>=0) left[i]=st[top];
            top++,st[top]=i;
        }
        return;
    }
    //求arr中元素右边第一个更小元素的下标，保存到right
    void getRight(vector<int> &arr,vector<int> &right)
    {
        int n=arr.size();
        int st[N],top=-1;
        for(int i=0;i<n;i++)
        {
            while(top>=0&&arr[st[top]]>arr[i])
            {
                right[st[top]]=i,top--;
            }
            top++,st[top]=i;
        }
        return;
    }
    int largestRectangleArea(vector<int> &heights)
    {
        heights.emplace(heights.begin(),0);
        heights.emplace_back(0);
        int ans=0,n=heights.size();
        vector<int> l(n),r(n);
        getLeft(heights,l);
        getRight(heights,r);
        for(int i=0;i<n;i++)
        {
            ans=max(ans,heights[i]*(r[i]-l[i]-1));
        }
        return ans;
    }
    int maximalRectangle(vector<vector<char>>& matrix) {
        int ans=0;
        int n=matrix.size(),m=matrix[0].size();//n行m列
        //求出第i层（以第i行为底）的柱状图高度序列
        vector<vector<int>> heights_of_line(n,vector<int>(m));
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(i==0) heights_of_line[i][j]=(matrix[i][j]=='1');
                else if(matrix[i][j]=='1') heights_of_line[i][j]=heights_of_line[i-1][j]+1;
                else heights_of_line[i][j]=0;
            }
        }
        for(int i=0;i<n;i++) ans=max(ans,largestRectangleArea(heights_of_line[i]));
        return ans;
    }
};