C++ 代码
#include<iostream>
using namespace std;
int n,h[100100],q[100100];
int main()
{
cin>>n;
for(int i=1; i<=n; i++)
{
scanf("%d",&h[i]);
}
int tt=0,res=0;
h[0]=-1;
for(int i=1; i<=n; i++)
{
while(tt&&h[q[tt]]<h[i])
{
if(tt>=2)
{
int l=i-q[tt-1]-1;
int hh=min(h[i],h[q[tt-1]])-h[q[tt]];
res+=l*hh;
// cout<<l<<' '<<hh<<' '<<res<<endl;
}
tt--;
}
// cout<<res<<' '<<h[i]<<endl;
q[++tt]=i;
}
cout<<res;
return 0;
}
题目本身不难,但是细节对于新手来说比较多,需要考虑全面
1.首先,考虑栈的意义是什么存什么,存了之后对计算体积有什么帮助呢?
2.如何计算体积,是要改变建筑本身的高度还是虚拟的堆到栈顶前一个的高度?
3.如何高度怎么堆?
解决这三个问题后,写题就会变得简单起来思路也会明确
看看我这个小菜鸡是怎么写的吧,,,,
1.挑一个方向,栈来存储能够形成一个密闭的u型容器的一边ex 3 2 1 4,其中3 2 1就是我们的栈了。
2.体积的计算,因为量太大了所以不能够想着改变高度来计算,所以我采用了直接计算法,用栈顶的前一个元素与其相比,取小的,每次计算完了栈顶前元素和栈顶一样高,再退栈即可,这样就计算出高度了,长度就是栈顶前元素和本身元素比较
因为 ex:0 10 4 6 5 0 9 8 10其中遍历到9时4这个元素不再栈里,所以当栈顶为6时与栈顶前面的元素比较距离就差了2,所以还是需要从栈顶前元素计算距离。
4.计算即可。
希望各位大佬多多指教,还有更好的方法请教教我。。。。。。