Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 使用单调栈进行维护

Posted by nimohunter at 2014-08-14 20:04:52 on Problem 2559
```栈内数字越来越大，这样在来一个小数字的情况，可以弹出比他大的数字，在这个时候进行计算答案，因为是越来越大的，所以可以保证从弹出点到当前数字都是可以构成矩形的。

#include <cstdio>
using namespace std;
const int MAX_N = 100005;
int deep[MAX_N], stack[MAX_N], A[MAX_N], n;
int main()
{
freopen("nimo.in", "r", stdin);
while (scanf("%d", &n) && n)
{
for (int i = 1; i <= n; i++)
scanf("%d", &A[i]);
A[n+1] = 0; n++;
stack[0] = 0;
long long ans = 0;
deep[0] = 0;
int top = 1;
for (int i = 1; i <= n; i++)
{
int depth = i;
while (A[i] < stack[top-1])
{
long long tmp = (long long)(i - deep[top-1]) * (long long)stack[top-1];
if (tmp > ans) ans = tmp;
depth = deep[top-1];
top --;
}

if (A[i] > stack[top-1])
{
stack[top] = A[i];
deep[top] = depth;
top ++;
}
}
printf("%lld\n", ans);
}
return 0;
}```

Followed by: