题意：给定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 ", 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 ", ans); } }