Largest Rectangle in a Histogram【POJ 2559】【单调栈】

POJ 2559

---

  题意就是说，有N个柱子，问我们最大的矩形面积是多少？简单明了。

  做法很多，笛卡尔树、dp、跳转、吧啦吧啦的……今天我们讲一下单调栈。

  我们任意的画一个矩形图，不难发现一件事，一个高度，我们以它为矩形的高的话，它的延伸的范围就是到上一个比他矮的点的后面一位以及到下一个比它矮的前面一位，就是它的水平宽度了。

  其中，有单调性。若是我们维护一个单调上升的栈，那么它的栈中的下面的一个应该就是那个比它小的了，也就是看到图中，如果我们要把13号柱子放进去，那么前面的一个柱子应该就是9号了，10、11、12、13是它的可以的范围。

  所以，我们的单调栈内维护这么几个东西，一是它的高度，这是判断它是否需要弹出栈的重要信息，二是它的深度，也就是它的可达最远的水平位置（相等值所在该区间段内所能达到的最远距离）。

  具体可以看一下Code：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
//#include <unordered_map>
//#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define MP(a, b) make_pair(a, b)
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 1e5 + 7;
int N, Stop;
ll h[maxN], ans;
struct node
{
    ll height, depth;
    node(ll h=0, ll d=0):height(h), depth(d) {}
}Stap[maxN];
inline void mono_queue()
{
    ll S = 0;
    for(ll i=1; i<=N; i++)
    {
        while(Stop && Stap[Stop].height > h[i])
        {
            S = Stap[Stop].height * (i - Stap[Stop - 1].depth - 1);
            ans = max(ans, S);
            Stop--;
        }
        if(h[i] > Stap[Stop].height)
        {
            Stap[++Stop] = node(h[i], i);
        }
        else Stap[Stop].depth = i;
    }
}
inline void init()
{
    Stop = 0; ans = 0;
    h[++N] = -1;
    Stap[0] = node();
}
int main()
{
    while(scanf("%d", &N) && N)
    {
        for(int i=1; i<=N; i++) scanf("%lld", &h[i]);
        init();
        mono_queue();
        printf("%lld\n", ans);
    }
    return 0;
}