关于POJ2559 Largest Rectamgle in Histogram的几个不同解法

单调栈1

使用单调栈，合并矩形然后再加入新矩阵。

# include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n;
long long h[N],w[N];
long long ans = 0;
stack <pair<long long,long long> > s; // {w,h}
int main(void)
{
    while(~scanf("%d",&n) && n)
    {
        for(int i = 1; i <= n; i++)
        {
            scanf("%d",&h[i]);
            w[i] = 1;
        }
        w[n + 1] = 0;
        h[n + 1] = 0;
        ans = 0;
        while(!s.empty()) s.pop();
        s.push(make_pair(1,h[1]));
        for(int i = 2; i <= n + 1; i++)
        {
            if(s.empty())
            {
                s.push(make_pair(1,h[i]));
                continue;
            }
            if(s.top().second <= h[i])
            {
                s.push(make_pair(1,h[i]));
            }
            else
            {
                long long totw = 0;
                while(!s.empty() && s.top().second > h[i])
                {
                    totw += s.top().first;
                    ans = max(ans,s.top().second * totw);
                    s.pop();
                }
                s.push(make_pair(totw,h[i]));
            }
        }
        printf("%lld
",ans);
    }
    return 0;
}

单调栈2

使用；两次单调栈，求出(l_i,r_i)，(l_i)表示从(i)往左的每一个(h_j <= h_i)的最远位置，即(min{x mid forall_{b ge x} a_b ge a_i}),(r_i)同理。

# include <bits/stdc++.h>
using namespace std;

# define int long long

const int N = 100010;

int n;
int h[N];
int l[N],r[N];
stack <pair<int,int> > s;
signed main(void)
{
    while(~scanf("%lld",&n) && n)
    {
        while(!s.empty()) s.pop();
        for(int i = 1; i <= n; i++)
            {
                scanf("%lld",&h[i]);
            }
            for(int i = 1; i <= n; i++)
            {
                while(!s.empty() && s.top().first >= h[i]) s.pop();
                if(!s.empty()) l[i] = s.top().second + 1;
                else l[i] = 1;
                s.push(make_pair(h[i],i));
            }
            while(!s.empty()) s.pop();
            for(int i = n; i >= 1; i--)
            {
                while(!s.empty() && s.top().first >= h[i]) s.pop();
                if(!s.empty()) r[i] = s.top().second - 1;
                else r[i] = n;
                s.push(make_pair(h[i],i));
            }
        long long ans = 0;
            for(int i = 1; i <= n; i++)
            {
                ans = max(ans,(long long)h[i] * 1ll * (r[i] - l[i] + 1));
            }
        printf("%lld
",ans);
    }
    
    return 0;
}

笛卡尔树

这个不讲了，不过是完全可做的。