概念：引入单调栈

请先阅读相关知识：单调队列

同样的，单调栈是一个为了维护单调性弹出元素的栈，他从栈顶到栈底是单调的。

模拟：了解单调栈

其实和本质单调队列一样。单调栈可以在时间复杂度为 $O(n)$ 的情况下，求解出某个元素左边或者右边第一个比它大或者小的元素。

下面我们以数组 [4, 3, 2, 5, 7, 4, 6, 8] 为例，模拟一下「单调递减栈」的进栈、出栈过程。具体过程如下：

以数组 $[4, 3, 2, 5, 7, 4, 6, 8]$ 为例，遍历顺序为从左到右。

步骤	待插入元素	操作	结果（左侧为栈底）	作用
1	4	4 入栈	$ [4] $	元素 4 的左侧无比 4 小的元素
2	3	4 出栈，3 入栈	$[3]$	元素 3 的左侧无比 3 小的元素
3	2	3 出栈，2 入栈	$[2]$	元素 2 的左侧无比 2 小的元素
4	5	5 入栈	$[2, 5]$	元素 5 的左侧第一个比 5 小的元素是：2
5	7	7 入栈	$[2, 5, 7]$	元素 7 的左侧第一个比 7 小的元素是：5
6	4	7 出栈，5 出栈，4 入栈	$[2, 4]$	元素 4 的左侧第一个比 4 小的元素是：2
7	6	6 入栈	$[2, 4, 6]$	元素 6 的左侧第一个比 6 小的元素是：4
8	8	8 入栈	$[2, 4, 6, 8]$	元素 8 的左侧第一个比 8 小的元素是：6

最终栈中元素为 [2, 4, 6, 8]。因为从栈顶（右端）到栈底（左侧）元素的顺序为 8, 6, 4, 2，满足递减关系，所以这是一个单调递减栈。

实现：代码单调栈

stack<int >L;
for(int i=1; i<=n; i++){
    while(!L.empty()&&h[L.top()]>=h[i]){
        L.pop();
    }
    if(L.empty()) l[i]=1;
    else l[i]=L.top()+1;
    L.push(i);
}