下载掌阅APP，畅读海量书库
立即打开
单调栈是指栈内部的元素具有严格单调性的一种数据结构，分为单调递增栈和单调递减栈。
单调栈具有以下两个性质。
（1）栈底到栈顶的元素具有严格单调性。
（2）栈的元素先进后出。
图2.3（a）所示是一个单调递减栈，图2.3（b）所示是一个单调递增栈，图2.3（c）所示既不是单调递减栈，也不是单调递增栈。
（a） （b） （c）
图2.3
单调栈的维护方法很简单，以单调递减栈为例，当一个元素要入栈时，从栈顶开始，把比该元素小的元素全部赶出栈后让该元素再入栈。例如入栈元素分别为4,5,3,7,4,6,3，维护过程如图2.4所示。
图2.4
单调栈的优势是时间复杂度是线性的，所有的元素只会入栈一次，而且一旦出栈后就不会再入栈了。
在单调递减栈可以找到左起第一个比当前数字大的元素。以图2.4所示的单调栈为例，依次观察栈中元素可以发现，左起第一个比3大的数是5，左起第一个比4大的数是7，左起第一个比6大的数是7……
同理，在单调递增栈可以找到左起第一个比当前数字小的元素。
有 n 个非负整数表示每个立方体柱子的高度，柱子宽度为1，计算能收集多少雨水。例如图2.5中，深色图形表示雨水，浅色图形表示柱子。
图2.5
第一行数据是一个整数 n （1＜ n ≤10000），第二行数据是 n 个数，表示柱子高度。
输出一个数，表示收集的雨水量。
12
0 1 0 2 1 0 1 3 2 1 2 1
6
根据只有左右两边柱子高、中间柱子低的区域才能收集雨水的特点，我们可以使用单调递减栈。一旦发现当前要入栈的元素大于栈顶元素，那就说明可能有能收集雨水的区域产生了，此时，当前要入栈的元素是右边界，要出栈的栈顶元素是水槽的最低点，栈顶左边的元素是水槽的左边界，如图2.6所示。
图2.6
实际上为了方便计算出水槽的宽度，单调栈里保存的并不是柱子的高度，而是柱子的位置。
参考程序如下。
已知 N 个人排队进入一个音乐会的现场，人们等得很无聊，于是他们开始转来转去，想在队伍里寻找自己的熟人。队列中任意两个人A和B，如果他们相邻或他们之间没有人比A或B高，那么他们就可以互相看得见。
试问有多少对人可以互相看见。
输入的第一行包含一个整数 N （1≤ N ≤500000），表示队伍中共有 N 个人。
输入的第二行有 N 个整数，表示人的高度，以nm（等于10 −9 m）为单位，每个人的身高都小于2 31 nm。这些高度分别表示队伍中人的身高。
输出一个数 S ，表示队伍中共有 S 对人可以互相看见。
7
2 4 1 2 2 5 1
10
为了更方便看透题目本质，可将输入样例中的第二行转换为图2.7所示的样式以观察其规律。
图2.7
显然对某个人来说，当右边某个人的身高比他高时，他就看不到更右边的人（不考虑左边的人是为了去重）。可以维护一个单调递减栈，使单调递减栈中的人不会出现被挡住的情况。当一个身高比在栈顶的人高的人要入栈时，先使栈中所有身高比他矮（不包括相同）的人出栈，如图2.8所示，出栈几个人，答案就加几个人。
图2.8
相同的元素虽然不出栈（因为有可能与后面入栈的人互相看见），但也要统计到答案中去。
参考程序如下。
