定义

• 单调递减栈：元素从栈顶到栈底单调递减的栈
• 单调递减栈：元素从栈顶到栈底单调递减的栈

应用

单调栈最常用的功能是可以求出一个元素向左（或向右）所能扩展到的最大长度，并不是说在这一段区间内是单调的，而是保证在该区间内该元素一定是最大或最小。

题目

POJ 3250 Bad Hair Day

题意

有$n$个人，问每一个人向右看能看到人的数量的总和（能看到的人身高比当前的人矮）。

题解

从后往前，维护一个单调递减栈来求每一个人右边的高度比它小的最近的位置即可。
code

POJ 2796 Feel Good

题意

有$n$个元素，问一个区间长度乘以区间最小值的最大值。

题解

也就是求每一个元素往左（右）值比它小的最近的位置。维护两次单调递减栈。
code

SCU 1773 Largest Rectangle in a Histogram

题意

给$n$个宽度为1的矩形，求最大连续矩形面积。

题解

矩形的面积等于区间长度乘以区间最小高度，做法和POJ 2796一样。