『单调栈』单调栈略讲

学习单调栈前提须知

单调栈顾名思义就是以栈的形式存储一个符合单调性的数列，通常用于考虑两种状态时，其中一种状态可以在某种情况下不需要考虑，且永久不需要考虑时，可以考虑单调栈

算法内容

竞赛需要用到的点

1、单调栈是想到很简单，没想到就很容易拿不到满分

2、单调栈的题不是很多，可能还会掺杂其他算法进行优化

单调栈求直方图中最大的矩形略讲

现在，给你\(n\)个矩形，每个矩形有一个高度\(length_i\)与宽度1，且两两矩形是紧挨着的，让你求这个直方图中的最大面积，这个最大面积一定是一个矩形，而并非一个不规则图形或其他图形。怎么做？我们这里很容易想到的就是有一种面积是由高度最低的矩形与所有矩形的宽度之和所形成的面积，那其他的又怎么做呢？那我们再考虑一下，如果当前矩阵高度是单调不下降序列并且其中某一个矩阵的高度是不满足单调不下降这个情况的话，那么我们可以轻易得出，对于高度和宽度两种状态，高度在某种特定条件下就会永久不需要考虑，什么时候？就是出现打破单调不下降的时候，此时该矩阵之前的所有高我们都不用考虑了，因为这之后都不会用到，我们仅仅会用到的是当前最低的高的值和前面所有矩阵所形成的宽度之和，这样以便在后面我们遇到更低的高的时候能够进行再次计算。

原理讲完了，我们就说下代码实现原理吧

1、给每个矩阵设高度，并且令第\(n+1\)有一个高度为0的矩阵，目的是为了让前面的矩阵完全弹出

2、循环从 1 到 n + 1，若当前数大于栈顶元素 那么就可以装进栈中

3、如果小于栈顶元素，那么我们就开始统计全部大于当前数的矩阵的答案，因为当前数前面的矩阵一定都满足一个单调不下降性，那么后面的宽度前面的矩阵一定都用得到，于是就可以很快的统计答案

4、宽度一定要保存到当前读入的一位，因为这之前的矩阵已经被删掉了一些了（或全部删完）

代码如下

//#define fre yes

#include <cstdio>
#include <iostream>

const int N = 100005;
int length[N], Stack[N], w[N];
long long ans;
int p;

int main() {
    static int n;
    while(scanf("%d", &n)) {
        if(n == 0) return 0;
        ans = 0; p = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &length[i]);
        }

        length[n + 1] = 0;
        for (int i = 1; i <= n + 1; i++) {
            if(length[i] > Stack[p]) {
                Stack[++p] = length[i];
                w[p] = 1;
            } else {
                int len = 0;
                while(Stack[p] > length[i]) {
                    len += w[p];
                    ans = std::max(ans, (long long)len * Stack[p]);
                    p--;
                } Stack[++p] = length[i], w[p] = len + 1;
            }
        } printf("%lld\n", ans);
    }
}