单调栈算法

单调栈：
单调栈就是栈内元素单调的栈结构吗。例如：序列 1，2，4，3，5。1，2，4依次入栈，因为元素3小于栈顶元素4，所以要出栈4，然后入栈3。得到1，2，3。
应用：
单调栈适用于求解多个序列的解且这多个序列存在公子序列的问题。例如力扣496：

分析：以序列[4 ，1，2]为例，暴力算法求解这道题目需要依次遍历序列[4，1，2]，[ 1 , 2], [ 2 ]。一个序列一个解，需要求解n个解，且这三个序列存在公共子序列。这种题目就可以用单调栈。
我总结的单调栈解题有三个步骤：
1，确定序列和遍历序列顺序，[4,1,2]例子的序列就是[4，1，2]，[ 1 , 2], [ 2 ]，遍历顺序就是[2]，[ 1 , 2]，[4，1，2]（其实就是确定从前往后遍历还是从后往前遍历，这道题是从后往前遍历）。
2.确定用单调递增栈还是单调递减栈，也就是如何排除一定不可能是解的元素。假设有一个序列[4,1,2,1]，元素2就可以将后面的元素1，以及一切比2小的元素排除掉，因为如果2是解则后面比他小的元素就不是题目要求的”右边第一个“，若2不是解则右边比2小的元素则也一定不是解。所以这道题大的元素可以将小的元素出栈，也就是单调递减栈。
3.确定用单调栈还是单调队列，简单说就是确定栈顶元素是当前所遍历的序列的解还是栈底元素是当前所遍历的元素的解。