51Nod - 1102 单调栈

题意：

第1行：1个数N，表示数组的长度(0 <= N <= 50000)第2 - N + 1行：数组元素A[i]。(1 <= A[i] <= 10^9)Output
输出最大的矩形面积Input示例
6215623Output示例
10
思路：
单调栈的模板题，枚举最低点，然后找到左右的边界。
代码：
#include <bits/stdc++.h>using namespace std;typedef long long ll;const int MAXN = 5e4 + 10;ll a[MAXN];int l[MAXN], r[MAXN];int main() {    int n;    scanf("%d", &n);    for (int i = 1; i <= n; i++)        scanf("%I64d", &a[i]);    stack <int> sta;    for (int i = 1; i <= n; i++) {        while (!sta.empty() && a[sta.top()] >= a[i]) sta.pop();        l[i] = sta.empty() ? 0 : sta.top();        sta.push(i);    }    while (!sta.empty()) sta.pop();    for (int i = n; i >= 1; i--) {        while (!sta.empty() && a[sta.top()] >= a[i]) sta.pop();        r[i] = sta.empty() ? n + 1 : sta.top();        sta.push(i);    }    ll ans = 0;    for (int i = 1; i <= n; i++)        ans = max(ans, (r[i] - l[i] - 1) * a[i]);    PRintf("%I64d/n", ans);    return 0;}