原题链接: 131. 直方图中最大的矩形
我首先用int存储答案,代码如下:
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
struct S
{
int h, num;
};
stack<S> s;
int n, tmp;
S ins, t;
int ans, inum;
int main()
{
int i;
while(true)
{
ans = 0;
cin >> n;
if(!n)
break;
cin >> tmp;
ins.h = tmp;
ins.num = 1;
s.push(ins);
for(i = 2;i <= n+1;i++)
{
if(i != n+1)
cin >> tmp;
else
tmp = 0;
inum = 0;
while(s.top().h > tmp)
{
t = s.top();
inum += t.num;
s.pop();
if(ans < t.h * inum)
ans = t.h * inum;
if(s.empty())
break;
}
ins.h = tmp;
ins.num = inum + 1;
s.push(ins);
}
cout << ans << endl;
}
return 0;
}
提交后发现int会爆掉,改成long long后用调试代码测试 一直显示 Memory Limit Exceeded 但是提交代码又显示AC。
求大佬解答