道长的算法笔记：单调栈查找前驱与后继

单调栈

　单调栈是一种满足单调性的栈结构，其维护单调性方式是弹出栈顶不符合的条件的元素，也就是说，单调栈存储的并非入栈的全部元素，相当一部分元素会被弹掉。使用单调栈通常是为了预处理算出数组每个元素的 前驱值、后续值，以此优化一些问题的复杂度。此处 前驱值、后继值 概念与线性表中所学的概念并不相同，此处的前驱值是指其前面第一个比它更大的元素，后继值是指其后面第一个比它更大的元素。

　这个方法稍加延伸，即可用于求解子数组边界，例如给定一个元素互不相同的序列 \(A\), 询问子数组有多少个以 \(A[i]\) 作为最小值或最大值的子数组。比较朴素的想法是使用双指针沿着位置 \(i\) 向其两侧扩展，看其边界能够到达多远，然后再以 \(i\) 作为分界线，根据乘法原理算出子数组的个数。