题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
秦淮案灯火阑珊
C++ 代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define N 100010
using namespace std;
long long h[N],w[N],stk[N]; //stk栈存储插入栈中直方图高度
//w存储每个直方图可扩展的宽度;
int n,top=0;
void work()
{
memset(stk,0,sizeof(stk)); //清空栈中原有内容
top=0; //栈顶指针回0
int i,wide;
long long res=0;
for(i=1;i<=n+1;i++)
{
if(stk[top]<h[i]) //新插入的直方图高度比栈顶直方图高
{
stk[++top]=h[i]; //直接将直方图插到栈顶之后
w[top]=1; //设置当前直方图扩展宽度为1
}
else //新插入的直方图高度与栈顶直方图高度相等或小于栈顶直方图高度
{
wide=0;
while(top>0&&stk[top]>=h[i]) //计算新插入直方图左侧所有高度大于等于新插入直方图的最大扩展面积
{
//while循环中的top>0是为了防止数组越界,当循环执行到i==n+1、top==0时,此时
//stk[0]=0>=h[n+1]=0,因此top--=-1,stk[-1]数组越界就会产生段错误
res=max(res,stk[top]*(w[top]+wide)*1ll);
wide+=w[top];
top--; //栈中所有高度大于等于h[i]的直方图出栈
}
stk[++top]=h[i]; //将第i个直方图插到栈中第1个高于小于它的位置之后
w[top]=wide+1; //更新第i个直方图的最大扩展宽度
}
}
cout<<res<<endl;
}
int main()
{
int i;
while(cin>>n,n)
{
for(i=1;i<=n;i++)
{
cin>>h[i];
}
//cout<<"数组:";
/*for(i=1;i<=n+1;i++)
{
cout<<h[i]<<' ';
}
cout<<endl;*/
h[n+1]=0;
work();
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla