LeetCode 84. 柱狀圖中最大的矩形 85. 最大矩形 221. 最大正方形

LeetCode 

84. 柱狀圖中最大的矩形

這道題的思路很明确，首先周遊整個數組，找到數值最小元素的位置和值，那麼包含這個位置的矩形的最大高度隻能是這個最小值，矩形的寬度最大為整個數組的長度，能夠存在的更大的矩形隻能是不包含這個位置的其他矩形，即在最小位置的左側和右側分别進行以上操作，直到數組邊界位置，用遞歸來解決，不斷松弛最大矩形的面積。

參考快速排序的時間複雜度，算法時間複雜度為O(nlogn).

class Solution {
public:
    void dfs(vector<int>& heights,int &ans,int l,int r)
    {
        int minn=-1,minid=1;
        for(int i=l;i<=r;i++)
        {
            if(minn==-1)
            {
                minn=heights[i];
                minid=i;
            }
            if(minn>heights[i])
            {
                minn=heights[i];
                minid=i;
            }
        }
        ans=max(ans,minn*(r-l+1));
        if(minid-1>=l)dfs(heights,ans,l,minid-1);
        if(minid+1<=r)dfs(heights,ans,minid+1,r);
        return;
    }
    int largestRectangleArea(vector<int>& heights) {
        int n=heights.size();
        int ans=0;
        if(n==0)return ans;
        int l=0,r=n-1;
        int minn=-1,minid=-1;
        for(int i=0;i<n;i++)
        {
            if(minn==-1)
            {
                minn=heights[i];
                minid=i;
            }
            if(minn>heights[i])
            {
                minn=heights[i];
                minid=i;
            }
        }
        ans=max(ans,minn*(r-l+1));
        if(minid-1>=0)dfs(heights,ans,l,minid-1);
        if(minid+1<n)dfs(heights,ans,minid+1,r);
        return ans;
    }
};
           

85. 最大矩形

這道題需要進行一個預處理，首先從倒數第二行開始直到第一行，如果matrix[i][j]=1，那麼matrix[i][j]+=matrix[i+1][j]，即通過o(nm)的預處理來獲得每個位置及其下方連續的1的個數，預處理完之後我們可以發現，每一行都形成了上一題中的柱狀圖數組，那麼調用n次柱狀圖數組即可求得最大面積。

算法的時間複雜度為O(nmlog(m))

class Solution {
public:
    void dfs(vector<int>& heights,int &ans,int l,int r)
    {
        int minn=-1,minid=1;
        for(int i=l;i<=r;i++)
        {
            if(minn==-1)
            {
                minn=heights[i];
                minid=i;
            }
            if(minn>heights[i])
            {
                minn=heights[i];
                minid=i;
            }
        }
        ans=max(ans,minn*(r-l+1));
        if(minid-1>=l)dfs(heights,ans,l,minid-1);
        if(minid+1<=r)dfs(heights,ans,minid+1,r);
        return;
    }
    int largestRectangleArea(vector<int>& heights) {
        int n=heights.size();
        int ans=0;
        if(n==0)return ans;
        int l=0,r=n-1;
        int minn=-1,minid=-1;
        for(int i=0;i<n;i++)
        {
            if(minn==-1)
            {
                minn=heights[i];
                minid=i;
            }
            if(minn>heights[i])
            {
                minn=heights[i];
                minid=i;
            }
        }
        ans=max(ans,minn*(r-l+1));
        if(minid-1>=0)dfs(heights,ans,l,minid-1);
        if(minid+1<n)dfs(heights,ans,minid+1,r);
        return ans;
    }
    int maximalRectangle(vector<vector<char>>& matrix1) {
        int n=matrix1.size();
        if(n==0)return 0;
        int ans=0;
        int m=matrix1[0].size();
        vector<vector<int>> matrix(n);
        for(int i=0;i<n;i++)matrix[i].resize(m);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                matrix[i][j]+=matrix1[i][j]-'0';
            }
        }
        for(int i=n-1;i>=0;i--)
        {
            for(int j=0;j<m;j++)
            {
                if(i==n-1)break;
                if(matrix[i][j]==1)
                {
                    matrix[i][j]+=matrix[i+1][j];
                }
            }
        }
        for(int i=0;i<n;i++)
        {
            ans=max(ans,largestRectangleArea(matrix[i]));
        }
        return ans;
    }
};
           

221. 最大正方形

這道題同上題一樣進行預處理，不同之處在于答案的更新上，在更新ans之前比較目前矩形高度和長度的關系，如果高度大于長度，那麼跳出遞歸(因為後續的高度肯定高于目前高度，後續寬度肯定小于目前寬度，也就是說後續肯定無解)，如果高度小于等于長度，那麼ans=minheight*minheight，其他同上題一樣。

算法的時間複雜度為O(nmlog(m))

class Solution {
public:
    void dfs(vector<int>& heights,int &ans,int l,int r)
    {
        int minn=-1,minid=1;
        for(int i=l;i<=r;i++)
        {
            if(minn==-1)
            {
                minn=heights[i];
                minid=i;
            }
            if(minn>heights[i])
            {
                minn=heights[i];
                minid=i;
            }
        }
        if(minn<=r-l+1)ans=max(ans,minn*minn);
        else return;
        if(minid-1>=l)dfs(heights,ans,l,minid-1);
        if(minid+1<=r)dfs(heights,ans,minid+1,r);
        return;
    }
    int largestRectangleArea(vector<int>& heights) {
        int n=heights.size();
        int ans=0;
        if(n==0)return ans;
        int l=0,r=n-1;
        int minn=-1,minid=-1;
        for(int i=0;i<n;i++)
        {
            if(minn==-1)
            {
                minn=heights[i];
                minid=i;
            }
            if(minn>heights[i])
            {
                minn=heights[i];
                minid=i;
            }
        }
        if(minn<=r-l+1)ans=max(ans,minn*minn);
        else return 0;
        if(minid-1>=0)dfs(heights,ans,l,minid-1);
        if(minid+1<n)dfs(heights,ans,minid+1,r);
        return ans;
    }
    int maximalSquare(vector<vector<char>>& matrix1) {
        int n=matrix1.size();
        if(n==0)return 0;
        int ans=0;
        int m=matrix1[0].size();
        vector<vector<int>> matrix(n);
        for(int i=0;i<n;i++)matrix[i].resize(m);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                matrix[i][j]+=matrix1[i][j]-'0';
            }
        }
        for(int i=n-1;i>=0;i--)
        {
            for(int j=0;j<m;j++)
            {
                if(i==n-1)break;
                if(matrix[i][j]==1)
                {
                    matrix[i][j]+=matrix[i+1][j];
                }
            }
        }
        for(int i=0;i<n;i++)
        {
            ans=max(ans,largestRectangleArea(matrix[i]));
        }
        return ans;
    }
};