#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int a[N];
int q[N]; //stack
int n;
LL calc(int h[], int n)
{
h[0] = h[n+1] = -1;
int tt=0;
LL max_area = 0;
q[0] = tt;
for (int i = 1; i<= n+1; i++)
{
while (tt>0 && h[i] < h[q[tt]])
{
LL top_value = h[q[tt]];
tt--;
LL l = q[tt];
LL r = i;
max_area = max(max_area, top_value*(r - l - 1));
}
tt++;
q[tt] = i;
}
return max_area;
}
int main()
{
while(cin>>n, n)
{
for (int i = 1; i <= n; i ++ ) cin >> a[i];
//scanf("%d", &a[i]);
cout << calc(a,n) << endl;
//memset(a, 0, sizeof a);
}
return 0;
}
从3516题提取部分代码形成。要注意本题的输入输出格式。用scanf可能会报错,要注意使用以上被注释掉掉格式。
因为考虑用stl容器可能会超时,利用数组q作为一个单调栈,tt来作为栈顶的指针,通过移动tt来确定当前最大的栈顶元素。
这才是我想要的题解
hxd大家互相学习