当前位置:   article > 正文

HDU 1506 Largest Rectangle in a Histogram(单调栈、笛卡尔树)

笛卡尔树的创建 单调栈 代码

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

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

 

  1. Sample Input
  2. 7 2 1 4 5 1 3 3
  3. 4 1000 1000 1000 1000
  4. 0
  5. Sample Output
  6. 8
  7. 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);
    }
}

 

转载于:https://www.cnblogs.com/ruthank/p/9727928.html

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/weixin_40725706/article/detail/793350
推荐阅读
相关标签
  

闽ICP备14008679号