题目链接：https://www.luogu.org/problemnew/show/SP1805

分析：

我们可以用一个单调栈由低到高来存储它的高度，并用数组对每个高度记录一下它前面（包括它自己）一共有多少个比它高的，可以看做它的左宽。

按顺序考虑每个高度h，如果h大于栈顶元素，则入栈，此时它大于左面全部的元素，并且将它的宽度初始为1。

否则，将栈内元素出栈，直到满足上面的条件。出栈时，我们要将出栈元素对之后问题的影响全部考虑进行处理，才能保证做法的正确性。

对于每个高度，它的作用无非两个：

1、以自己作高，向外扩展

2、以别人作高，自己被扩展

由于我们数组中已经记录了某个高度的左宽，所以我们只需要考虑它能不能向右扩展，如果能，能扩展多少？

首先，对于第一个出栈的元素来说，它的右宽一定是0。

然而对于第二个，它的右边有刚才出栈的元素，而且刚才出栈元素的总宽中所涉及的元素一定可以被自己扩展，所以自己的右宽为刚才出栈元素的总宽。

同理可知，第三个出栈元素的右宽为第二个出栈元素的总宽。依次类推。

而当h大于栈顶元素时，h的左宽应该是上次出栈元素的总宽+1（自己），然后入栈。

最后时，将所有元素出栈，即可将所有情况考虑。

代码.吹泡泡cpp

#include<cstdio> #include<cmath> #include<cstring> using namespace std; struct ben { long long h,w; }a[100005]; long long n,h[200005],ans; void ddz() { ans=0; int top=0; h[n+1]=0; for(int i=1;i<=n+1;i++) { if(h[i]>a[top].h) { a[++top].h=h[i]; a[top].w=1; } else { long long qaq=0; while(a[top].h>h[i]) { qaq+=a[top].w; ans=fmax(ans,qaq*a[top].h); top--; } a[++top].h=h[i]; a[top].w=qaq+1; } } printf("%lld\n",ans); } int main() { while(1) { scanf("%lld",&n); if(n==0) break; memset(h,0,sizeof(h)); for(int i=1;i<=n;i++) scanf("%lld",&h[i]); ddz(); } return 0; } 额，和楼下一位大佬的代码很像啊

转载于:https://www.cnblogs.com/vercont/p/10210024.html

相关资源：JAVA上百实例源码以及开源项目