HDU 1506 Largest Rectangle in a Histogram（单调栈、笛卡尔树）

题意：给定n个连续排列的矩形的高，矩形的宽都为1。问最大矩形覆盖。

例如：n = 7，h[i] = (2 1 4 5 1 3 3)，最大覆盖为8。

 

Sample Input
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0
 
Sample Output
8
4000

 

 

题解：

首先可以确定，最大矩形的高一定等于某个矩形的高，宽一定等于某个矩形可以向两边最大可以延伸到的范围。

维护一个非降序的单调栈，然后依次枚举矩形的高 h[i]。

当 h[i] > top()时，说明 h[i] 向左最多可以延伸到 top() + 1，然后将 i 入栈。

当 h[i] < top()时，说明 top 向右最多可以延伸到 i - 1，为了满足栈的单调，栈顶元素要不断出栈，然后按 h[i] > top()的情况处理。

最后扫一遍，找最大的 (r[i] - l[i] + 1) * h[i]，就是答案。

 

h[i] == top() 呢？不用管。

可以看出，对于有两个以上的矩形等价（这里的等价指的是，矩形高度相同，他们的最大延伸范围也相同）时，上面处理得到的 l[i] 和 r[i] 只有其中一个的答案会是他们最大的延伸范围，所以并不影响答案。所以维护的单调栈可以是单调不降的，也可以是单调递增的。

例如：4 4 4 4，上面求出的延伸范围是(1, 4) (2, 4) (3, 4) (4, 4)。

 

 

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;
typedef long long LL;
const int maxn = 100010;
const LL INF = 1e16;

int a[maxn];
LL l[maxn], r[maxn];

int main()
{
    int n;
    while(~scanf("%d", &n) && n)
    {
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

        stack<int> st;
        st.push(0), a[n+1] = 0;
        for (int i = 1; i <= n+1; i++)
        {
　　　　      //若是这里改成 >= 来维护单调递增的栈的话，判断应该加一个 && （a[st.top() | a[i]）,防止栈空。
            while(a[st.top()] > a[i]) 
                r[st.top()] = i-1, st.pop();
            l[i] = st.top()+1;
            st.push(i);
        }

        LL ans = -INF;
        for (int i = 1; i <= n; i++)
            ans = max(ans, 1ll * (r[i]-l[i]+1) * a[i]);

        printf("%lld\n", ans);
    }
}

 

 

另一种做法就是笛卡尔树了。

笛卡尔树满足的条件：

1、左子树的下标 < 根节点 < 右子树

2、根节点的值是子树中所有点的最值。

可以看出，对一颗笛卡尔树中序遍历即可得到原序列。

故此题可以构造一个笛卡尔树，答案就是所有子树中 MAX（子树结点 × 根节点的值）。

 

笛卡尔树可以借助单调栈构建：

按照序列的顺序，每加入一个 a[i] 时，

若栈顶元素 > a[i]，则不断弹出栈顶，使栈满足单调。将最后一个被弹出的做为 i 的左儿子。（因为这一段被弹出的下标都小于 i ，并且值都大于 a[i]）

然后将 i 入栈，做为原本栈顶的儿子。

 

时间复杂度O(n)。

 

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;
typedef long long LL;
const int maxn = 100010;
const LL INF = 1e16;

int a[maxn], lson[maxn], rson[maxn], fa[maxn];
LL dp[maxn];
LL ans, tmp;

LL DP(int id)
{
    if (id == 0) return 0;
    if (dp[id]) return dp[id];
    dp[id] = DP(lson[id]) + DP(rson[id]) + 1;
    ans = max(ans, 1ll * dp[id] * a[id]);
    return dp[id];
}

int main()
{
    int n;
    while(~scanf("%d", &n) && n)
    {
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

        stack<int> st;
        memset(lson, 0, sizeof(lson));
        memset(rson, 0, sizeof(rson));
        memset(dp, 0, sizeof(dp));
        memset(fa, 0, sizeof(fa));

        for (int i = 1; i <= n; i++)
        {
            if (!st.empty() && a[st.top()] > a[i])
            {
                while (!st.empty() && a[st.top()] > a[i])
                    tmp = st.top(), st.pop();
                lson[i] = tmp, fa[tmp] = i;
            }
            if (!st.empty()) rson[st.top()] = i, fa[i] = st.top();
            st.push(i);
        }

        ans = -INF;
        for (int i = 1; i <= n; i++) if (!fa[i]) DP(i);

        printf("%lld\n", ans);
    }
}