单调栈

1. 简介

单调栈是一种用来解决首递增序列问题的数据结构，其满足从栈顶元素到栈底元素单调的性质。单调栈还可以用来解决求矩形统计图中最大内矩形面积的问题，进一步可以用来求最小矩阵和问题。

2. 概念

• 首递增序列

对于序列 a_1,a_2,\cdots,a_N，定义从左往右 a_i的首递增序列为 a_{b_0}=a_i,a_{b_1},a_{b_2},\cdots,a_{b_m}​​，满足 \forall j \in (0, m] ，都有 \forall 1 \leq k \lt b_j, a_{b_{j-1}} \geq a_k \wedge a_k \lt a_{b_j} 。

• 首递减序列

对于序列 a_1,a_2,\cdots,a_N​，定义从左往右a_i​ 的首递减序列为从右往左a_i的首递增序列。

• 单调递增栈

从栈顶元素到栈底元素单调递增。

• 单调递减栈

从栈顶元素到栈底元素单调递减。

3. 思想

3.1 求首递增序列

以求数组 a 中所有元素的首递减序列的长度的最大值为例。

• 利用单调递增栈，从左往右扫一边数组 a，对于当前处理的元素 a[i]：

1. 如果 a[i]小于栈顶元素或栈顶为空，则直接将 a[i] 压栈。
2. 如果 a[i] 大于等于栈顶元素，则一直弹栈直到栈顶元素小于 a[i]，再将a[i] 压栈。
3. 则 a[i] 的首递减序列长度即为将 a[i]压栈后的栈长度。

• 每次处理完一个元素a[i]，更新一下最大值即可。

3.2 求矩形统计图最大内矩形面积

以下图为例，求出矩形统计图最大内矩阵面积，易知最大面积为 8 。

• 将矩形统计图每个条形矩形的高作为数组的值，易知最终的结果一定是某个条形矩形的高乘以一定宽度。
• 从左往右扫描该高度数组，当数组递增时，我们无法计算出基于当前位置对应的条形矩形的高的最大内矩阵面积，因为后面还可能存在比当前位置对应的条形矩形的高更高的条形矩形；但如果数组在当前位置递减了，对于基于当前位置的前一个位置对应的条形矩形的高作为内矩形的高的情况，则该内矩阵的面积已然可以确定。因为当前位置对应的条形矩形的高要更小，所以后续的条形矩形的高已然和以当前位置的前一个位置的条形矩阵的高为高的内矩阵无关。即以当前位置前一个位置对应的条形矩形的高作为内矩形的高时，内矩形的宽度已经确定了，即当前位置的数组下标到当前位置前一个位置的前一个有效位置（即还没有计算基于对应条形矩形作为内矩形的高的内矩形面积的位置）的数组下标。
• 于是便可以处理在当前位置前面且比当前位置的条形矩形的高更高或相等的所有位置（即计算以它们的高为高的内矩形面积），后续就可以忽略它们了（即它们无效了）。
• 对于在当前位置前面且比当前位置对应的条形矩形的高更低的位置还无法处理，因为还无法确定它们最终可能的内矩形面积大小。
• 直到扫描完整个数组，将从保留下来的有效位置的最后一个开始往前处理，处理方式和第三步一样，计算内矩形宽度时当前位置就是数组的最大下表。

而这个过程刚好符合单调递减栈的性质，于是乎就可以用单调递减栈来维护所有有效位置，处理完的无效位置就被弹出栈了。即：

• 若栈顶元素不比当前元素值小，则计算基于栈顶元素值为内矩形高的内矩形面积大小，宽度为当前元素的下标值到栈顶下一个元素的下表值。计算完后将栈顶元素弹出栈，然后继续判断栈顶元素与当前元素的大小。
• 若栈顶元素比当前元素值小，则说明还无法确定基于栈顶元素值为高的内矩形的面积，故直接压栈。
• 扫描到最后一个元素后，再没有其他元素，故直接将栈中元素逐个弹出，并计算基于栈顶元素值为内矩形高的内矩形面积大小，宽度为当前元素（最后一个元素）的下标值到栈顶下一个元素的下表值。

4. 模板

【注】以下模板仅给出最原始的单调栈结构，可以用来解决简单的首递增问题。对于进一步解决矩形统计图最大内矩形面积的问题，需要在弹栈入栈时做额外的操作，关于具体的应用可以参考 P4147「玉蟾宫」。

#include <bits/stdc++.h>
using namespace std;

#ifndef _MSTACK_
#define _MSTACK_
#define ll int
#define MAXN 100005

// 比较元素
template < typename T >
struct Compare {
    bool operator () (const T & a, const T & b) {
        return a < b;   // 从左往右首递增序列（单调递减栈）
        return a > b;   // 从左往右首递减序列（单调递增栈）
    }
};
// 单调栈
template < typename T, typename F = Compare<T> >
struct MStack{
    ll depth;       // 栈深
    T stack[MAXN];  // 单增栈
    F cmp;
    MStack():depth(0) {}
    // 二分查找
    ll find(T x, ll l, ll r) {
        if(l == r)  return l;
        ll m = (l+r) >> 1;
        if(cmp(stack[m], x)) {
            return find(x, m+1, r);
        } else {
            return find(x, l, m);
        }
    }
    // 压栈
    T push(T x) {
        // // 方法一
        // // 顺序弹栈 O(n)，整体 O(2n)
        // while(depth && !cmp(stack[depth-1], x))   --depth;
        // stack[depth++] = x;
        // return x;

        // 方法二
        // 二分查找 O(lg(n))，整体 O(nlg(n))
        if(!depth || cmp(stack[depth-1], x)) {
            stack[depth++] = x;
            return x;
        }
        ll pos = find(x, 0, depth-1);
        T t = stack[pos];
        stack[pos] = x;
        depth = pos + 1;
        return t;
    }
    // 弹栈
    T pop() {
        return stack[--depth];
    }
    // 清空栈
    void clear() {
        depth = 0;
    }
};
#endif