题意是给定一定量的木板，长度不一，按顺序排成一排，问够成的图形中能容纳的最大的矩形面积是多少。
思路 dp / 单调栈 首先说dp的思路，因为对于每一个木板，我们都有一个高度，主要是看这个高度能够向左向右延伸多远。如果一个木板左边的 木板能够大于当前的木板，则当前的木板的高度就能延伸到左边的木板，依次类推，我们其实就是不断寻找左边木板最多能延伸 到哪，因为如果左边木板比当前木板的高度大的话，它延伸到哪，当前木板一定可以延伸到哪。同理对向右延伸也是一样。 其次用单调栈。以左向为例，我们注意到如果当前木板之前木板的高度小于当前木板的高度，当前木板的高度就被截断，不能延伸。 我们就可以构造栈底到栈顶依次递增的单调栈，如果当前栈顶的元素大于当前木板的高度，就代表有之前的木板可以让当前木板的 矩形进行延伸。栈顶元素其实就是限制了高度，延伸的判断决定了高度必须是依次递减的。 给 #include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <deque> using namespace std; const int maxn = 100000 + 10; int a[maxn], L[maxn], R[maxn]; int n; typedef pair<int, int> pii; typedef long long LL; int main() { while(scanf("%d", &n) == 1 && n){ deque<pii> Q; for(int i = 1; i <= n; ++i){ scanf("%d", &a[i]); L[i] = R[i] = i; } a[0] = a[n + 1] = -1; Q.push_back(pii(-1, 0)); for(int i = 1; i <= n; ++i){ int v = a[i]; while(!Q.empty()) { pii u = Q.back(); if(v > u.first) { L[i] = u.second + 1; break; } Q.pop_back(); } Q.push_back(pii(v, i)); } Q.clear(); Q.push_back(pii(-1, n + 1)); for(int i = n; i >= 1; --i){ int v = a[i]; while(!Q.empty()){ pii u = Q.back(); if(v > u.first){ R[i] = u.second - 1; break; } Q.pop_back(); } Q.push_back(pii(v, i)); } LL maxv = 0; for(int i = 1; i <= n; ++i){ maxv = max(maxv, ((LL)R[i] - L[i] + 1) * (LL)a[i]); } printf("%lld\n", maxv); } return 0; } 出单调栈的代码