AcWing 3194：最大的矩形 ← 笛卡尔树

【题目来源】
https://www.acwing.com/problem/content/3197/

【题目描述】
在横轴上放了 n 个相邻的矩形，每个矩形的宽度是 1，而第 i（1≤i≤n）个矩形的高度是 hi。
这 n 个矩形构成了一个直方图。
例如，下图中六个矩形的高度就分别是 3,1,6,5,2,3。

请找出能放在给定直方图里面积最大的矩形，它的边要与坐标轴平行。
对于上面给出的例子，最大矩形如下图所示的阴影部分，面积是 10。

【输入格式】
第一行包含一个整数 n，即矩形的数量。
第二行包含 n 个整数 h1,h2,…,hn，相邻的数之间由空格分隔。hi 是第 i 个矩形的高度。

【输出格式】
输出一行，包含一个整数，即给定直方图内的最大矩形的面积。

【输入样例】
6
3 1 6 5 2 3

【输出样例】
10

【数据范围】
1≤n≤1000,
1≤hi≤10000
经实测 hi 在官网的实际范围是 1≤hi≤40000，这与其给出的题面描述不符，属于官网出题人的失误，也因此卡住了一些同学的代码，望大家加以注意。

【算法分析】
● 如何构建笛卡尔树：https://blog.csdn.net/hnjzsyjyj/article/details/138400888

● 笛卡尔树是一种非常特殊的二叉查找树（BST）。每个结点有两个信息 (pri, val)，如果只考虑 pri，它是一棵二叉查找树，如果只考虑 val，它是一个小根堆。
一般地，构建笛卡尔树时，我们按第一关键字 pri 排序（很多时候，pri 值即为数组下标）。本题中，pri 值就是数组下标，无需排序，直接按给定的高度建树。

● 如何构建笛卡尔树？（参考于：https://wansuanfa.com/index.php/776）
笛卡尔树的构建步骤如下：（构建前需对 pri 递增排序，或选择数组元素的默认递增下标）
（1）用数组中的第一个元素创建根结点。
（2）遍历数组中剩下的元素，如果新元素比根结点小，让根结点成为新结点的左子结点，然后新结点成为根结点。
（3）如果新结点比根结点大，就从根结点沿着最右边这条路径一种往右走，直到找到比新结点大的结点 node ，也可能没找到。如果找到，就让新结点替换 node 结点的位置，让 node 结点变成新结点的左子结点。如果没找到，就让新结点成为最后查找的那个结点的右子结点。
（4）重复上面步骤（2），（3），直到元素全部遍历完。

● 构建笛卡尔树的关键点解析（参考于：https://wansuanfa.com/index.php/776）
（1）如果新结点比根结点小，根据小根堆（元素的值满足小根堆）的性质，那么新结点一定是根结点的父节点。又因为根结点的下标比新结点小，根据二叉查找树（元素的下标满足二叉查找树）的性质，根结点只能是新结点的左子树。
（2）如果新结点比根结点大，那么新结点只能往右边查找，不能往左边，如果往左边就不满足二叉查找树的性质了。如果比右子结点还大，就继续往右，所以只要比右子结点大就会一直往右。如果比右子结点小，根据小根堆的性质，新结点就会成为这个右子结点的父结点，根据二叉查找树的性质，这个右子结点要成为新结点的左子结点（因为右子结点的下标比新结点小）。

下图为构建笛卡尔树的过程示意图。通过构建过程，易知如何维护笛卡尔树每个结点的两个信息 (pri, val)，以及如何保障笛卡尔树具有二叉查找树和堆的双重特性。由图可知，构建方法为以 val 值作为结点，并用其构建小根堆。当需要调整时，以结点插入顺序（或称优先级 pri）为依据，将对应结点置于左子树或右子树，从而保证“如果只考虑 pri，它是一棵二叉查找树”的特性。
简言之，一棵笛卡尔树，val 决定了结点的值，pri 决定了结点的位置。

【算法代码】

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

const int maxn=1005;
int n;
int top;
int h[maxn],w[maxn];
int ls[maxn],rs[maxn],stk[maxn];

int buildCartesianTree() {
    for(int i=1; i<=n; i++) {
        int t=top;
        while(t && h[stk[t]]>h[i]) t--;
        if(t) rs[stk[t]]=i;
        if(t<top) ls[i]=stk[t+1];
        stk[++t]=i;
        top=t;
    }
    return stk[1];
}

int ans=0;
void dfs(int x) {
    w[x]=1;
    if(ls[x]) {
        dfs(ls[x]);
        w[x]+=w[ls[x]];
    }
    if(rs[x]) {
        dfs(rs[x]);
        w[x]+=w[rs[x]];
    }
    ans=max(ans,w[x]*h[x]);
}

int main() {
    cin>>n;
    for(int i=1; i<=n; i++) cin>>h[i];

    int root=buildCartesianTree();
    dfs(root);
    cout<<ans;
    return 0;
}

/*
in:
6
3 1 6 5 2 3

out:
10
*/

【参考文献】
https://www.cnblogs.com/asdfsag/p/10540265.html
https://wansuanfa.com/index.php/776
https://www.acwing.com/solution/content/98293/
http://www.manongjc.com/detail/12-bqkgltddigmoafg.html
https://blog.csdn.net/hnjzsyjyj/article/details/138400888
https://www.cnblogs.com/silentEAG/p/11555056.html