Codevs2491玉蟾宮

http://codevs.cn/problem/2491/

求最大子矩形面積，方法很多。

首先介紹一個cgold的O（n^3）暴力做法：

http://blog.csdn.net/qq_36312502/article/details/77334624

除此之外這裡還收集了三種方法，但首先要明确如下幾點：

本題的統計思路：分别計算以每一行為底所能得到的最大子矩形面積 。

無論什麼方法，我們都是通過确定一個已知高度的一列F向左向右擴充的邊界來确定一個矩形的。

方法一：單調棧

我們建立棧内元素高度嚴格遞增的單調棧s，用于存儲周遊到的每一列F的高度，每次周遊到新的一列則判斷：

1.若目前列的高度大于棧頂元素則加入棧中，符合棧中元素高度嚴格遞增的條件。

2.若目前列的高度小于棧頂元素則依次彈棧，至目前一列的高度為棧中最高 ，維護棧中元素高度嚴格遞增的條件。

3.周遊完成後再将棧内元素依次彈出。

在彈棧時計算将要彈出的一列向左向右（高度不變）擴充出的矩形面積，答案對每個矩形面積取max即可。

如何計算呢？

我們另外開一個對應的棧l，儲存s中對應列向左擴充的長度。

确定一列的l值時有如下兩種情況

1.符合單調性的一列加入，可向左擴充的距離隻有其本身1，l中記為1。

2.高度小于棧頂元素的一列加入，對于棧内高度大于等于目前列的元素來說，其向右可擴充的長度為其後加入的列的個數，我們記為len。那麼我們就可以在彈棧時得到棧中每一個高度大于等于目前列的元素對應的這個len去計算他們擴充出的最大子矩形面積。對于目前列，我們在彈棧完成後将其加入棧中，其在l中對應的值為len+1。

為什麼是len+1呢？

因為雖然我們将高度大于等于目前列的元素彈出棧了，但事實上在原圖中他們依舊是存在的，仍可以為目前列貢獻向左擴充的長度，然後加上其本身的距離1，就是len+1了。

代碼

#include<iostream>//棧内元素高度嚴格遞增的單調棧 
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,top,len,ans;
int mp[][],s[],l[];
char c;
void find(int h[])
{   
    for(int j=;j<=m;j++)
    {
        if(h[j]>s[top])//若高度大于棧頂元素則加入棧中 
        {
            s[++top]=h[j];
            l[top]=;//記錄新加入了一列 
        }
        else
        {
            len=;
            while(top&&h[j]<=s[top])//彈棧至目前一列的高度為棧中最高 
            {
                len+=l[top];//記錄将要彈出棧的一列,其在圖中向左可擴充的長度+目前向右可擴充的長度---也是向右可擴充的最長長度 
                ans=max(ans,len*s[top]);//取其面積更新答案 
                top--;
            }
            s[++top]=h[j];
            l[top]=len+;//記錄目前一列可向左擴充的大小 
        }
    }
    len=;
    while(top!=)//将剩餘列依次彈棧,處理其可擴充的答案的方法同上 
    {
        len+=l[top];
        ans=max(ans,len*s[top]);
        top--;
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=;i<=n;i++)
    {
        for(int j=;j<=m;j++)
        {
            c=getchar();
            while(c<'F'||c>'R')
            c=getchar();
            if(c=='F')
            mp[i][j]=mp[i-][j]+;//mp[i][j]記錄第i行第j列F的高度 
        }
    }
    for(int i=;i<=n;i++)//計算以每一行為底所能得到的最大子矩形面積 
    find(mp[i]);
    printf("%d",ans*);
    return ;
}
           

方法二：懸線法

首先處理出每一個點對應列（懸線）向左和向右可擴充到的邊界記為l[i][j]和r[i][j]。

然後對于每一個合法的點，處理其上方的點的邊界對其邊界的影響，即對兩點共同所處的矩形左右邊界确定的影響，具體操作為兩點邊界值取min。

這樣實際上來說，是将此點作為其上方的點所處矩形向下的擴充，而以此點原有邊界為邊界的矩形,則由與此點同行的其他不受上方點限制(上方點不合法或邊界更寬松)的點統計，因為我們會處理每個點擴充到的矩形,故不會存在遺漏情況，可以保證正确性。

代碼

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
const int maxn=+;
int h[maxn][maxn],l[maxn][maxn],r[maxn][maxn];
bool mmp[maxn][maxn];
int n,m;
int main()
{
    char ch[];
    scanf("%d%d",&n,&m);
    for(int i=;i<=n;i++)
        for(int j=;j<=m;j++)
        {
            scanf("%s",ch);
            if(ch[]=='F') mmp[i][j]=;
            else if(ch[]=='R') mmp[i][j]=;
        }
    for(int i=;i<=n;i++)
    {
        for(int j=;j<=m;j++)
        {
            if(mmp[i][j]) l[i][j]=l[i][j-]+;//處理每一個點向左可擴充到的邊界 
        }
        for(int j=m;j>=;j--)
        {
            if(mmp[i][j]) r[i][j]=r[i][j+]+;//處理每一個點向右可擴充到的邊界 
        }
    }
    for(int i=;i<=n;i++)
    {
        for(int j=;j<=m;j++)
        {
            if(mmp[i][j])
            {
                h[i][j]=h[i-][j]+;
                if(mmp[i-][j])
                {
                    l[i][j]=min(l[i][j],l[i-][j]);
                    //處理其上方的點的邊界對兩點共同所處的矩形的影響 
                    r[i][j]=min(r[i][j],r[i-][j]);
                    //将此點作為其上方的點所處矩形向下的擴充 
                }                                 
            }
        }
    }
    int ans=;
    for(int i=;i<=n;i++)
        for(int j=;j<=m;j++)
            ans=max(ans,h[i][j]*(l[i][j]+r[i][j]-));//處理每個點擴充到的矩形
    printf("%d\n",ans*);
    return ;
}
           

但要注意這個算法的空間複雜度的是比較高的。

方法三：單調棧+懸線法

我們通過維護單調棧确定棧頂元素向左，向右擴充的的邊界，但并非在彈棧過程中計算面積，而是在每一列的邊界确定後周遊一遍計算面積。

對于某一行中的各列我們先需要從左向右進行一遍單調棧的操作：

1.若目前列的高度大于棧頂元素則加入棧中。

2.若不然則可确定棧頂元素不可能再向右擴充，則其右邊界為目前列的編号j-1即棧頂元素對應編号。

3.周遊完成後，棧内剩餘元素的右邊邊界都為列數m，這是顯而易見的。

同理我們再從右向左進行一遍單調棧的操作就可以确定每一列的左邊界了。

之後再周遊各列計算矩形面積即可。

代碼

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,mmp[][],r[],l[],s[],top,ans;
string x;
inline void push(int x)
{
    s[++top]=x;
    return;
}
inline void pop()
{
    s[top--]=;
    return;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=;i<=n;i++)
        for(int j=;j<=m;j++)
        {
            cin>>x;
            if(x=="F")
            mmp[i][j]=mmp[i-][j]+;//mp[i][j]記錄第i行第j列F的高度 
        }
    for(int i=;i<=n;i++)
    {
        for(int j=;j<=m;j++)
        {
            while(mmp[i][j]<mmp[i][s[top]])
            {
                r[s[top]]=j-;//棧頂元素可向右擴充的邊界确定 
                pop();
            }
            push(j);
        }
        while(top>)
        {
            r[s[top]]=m;//右邊界即為原圖最右端 
            pop();
        }
        for(int j=m;j>=;j--)
        {
            while(mmp[i][j]<mmp[i][s[top]])
            {
                l[s[top]]=j+;//棧頂元素可向左擴充的邊界确定 
                pop();
            }
            push(j);
        }
        while(top>)
        {
            l[s[top]]=;//左邊界即為原圖最左端 
            pop();
        }
        for(int j=;j<=m;j++)
        ans=max(ans,(r[j]-l[j]+)*mmp[i][j]);//對于每一個列考慮可以擴充成多大的矩形,其高度至高為目前列的高度 
    }
    printf("%d",*ans);
}
           

正如開篇所說，“無論什麼方法，我們都是通過确定一個已知高度的一列F向左向右擴充的邊界來确定一個矩形的”，三種方法本質上并無差別，差别來着實作方法。對于一種解題思路不妨嘗試考慮不同的實作，同時，也要綜合考量算法對時間複雜度，空間複雜度和代碼複雜度的影響。