单调栈：

问题描述：给定一个数组 请确定每个元素左右距离最近的比它大的数字

常规想法：  到某一个元素时   通过两个for 分别获取其左边比它大的和右边比他大的数字  时间复杂度为O(n2)

最优解思路（单调栈）：

1  一个按照从大到小顺序排序的栈结构    若在压栈过程中发现要压栈的元素和栈顶的元素相比要大  则弹出当前栈顶元素 并从开始弹出处记录   之后继续弹出的下一个即为距离最近的一个元素

注意： 到数组末尾时  但是栈中依然有元素  则此时元素弹出 右为null 而左边为栈中的下一元素

记得 观察 这个元素弹出的驱动是啥？   之前的是因为右边要压栈的比栈顶元素要大  所以可以弹出并记录信息

特殊情况：若出现相等元素情况 则将下标放在一起  等到出现比它们大的数字时再依次弹出即可

具体应用：

1   构造数组的maxtree:

思路1 ： 按照大根堆思路建立  O(N)

思路2：  单调栈

按照单调栈的思路找到每个元素左右最近比它大的元素---分以下几种情况进行讨论：

  1  若一个元素左右均是null 则它是全局最大的  直接作为根节点

  2  若一个元素左或者右 只存在一个  则只具有唯一的父节点

 3   若一个元素左右两个元素均存在 则选择其中最小的那个作为父节点

注意：  一定只能构成一棵树  不会成为多叉树或者森林

代码：

2    求最大子矩阵的大小：

类似的，下图的直方图 ，以每个矩阵的中心高度为杠---然后分别向左右去扩展 ---并记录能够达成的最大格子数目

解法:     用单调栈---从小到大的顺序   若压栈元素<当前栈顶元素  则弹出栈顶元素 

如果栈下面没有元素 则一定能够到达左边界  右边界就是那个压栈元素所在值    

若到最后栈里有元素  但是没有主动让元素弹出的右端元素  则可以最右到达右边界  左边就是下面的元素

分析时间复杂度： O（n*m ) 就是遍历一遍矩阵

涉及到的逻辑：

1   栈应该是下小上大的  跟之前的几个题刚好是相反的   （压入情况）

2   不符合1的逻辑 则需要弹出的逻辑：

3  总结：

代码：

由直方图求解最大矩形：

原问题的主函数：

3  校招真题：

给定一个数组  数组元素组成一个首尾相连的环形  有以下几个规则：

1  相邻可见   

2  若元素i到元素j之间的路上不存在比 k（i与j之间小的那个数字）大的元素 则 认为相互可见

 要求 给定数组  求能相互可见的山峰有多少对~

1  先考虑没有重复元素的数组：

推导的结论公式：

推导过程：

一共n个点  除去最高和次高的点   n-2  这n-2个点   每个都存在两对(肯定在左边有一个比自己大的停止，右边同理）

---->  2*(n-2)----> 次高到最高这一条+1 --->2*(n-2)+1=2n-3

2 原问题（可能有重复元素）：

则用到从大到小的单调栈 

步骤： 先找到数组中最大的数--然后按照一侧顺序开始入栈 

           保证入栈的第一个元素一定是最大的那个

举例说明流程：

      5 3 4 3 4  4 4 5 --- 栈中遇到重复元素   计数器+1即可

出现了多个4后 产生了多少山峰？

类似于   5 4 4 4 4 5     4之间每两个可以相互看见      ----C4(2)   

                                   每一个4 分别到左边（右边） 的5   ----2*4

总结规律：

每次元素弹出 就结算 它能看见的山峰个数

若栈中不为空 但是也无法主动弹出时（即一直都是小的入栈）：

栈中除了倒数1，2条 其他均保持原有规则

而倒数1，2 条特殊情况：

1） 若最后一条记录为1  （计数）

    则构成环   Cm(2) +m

2)   若最后一条记录不为 1 （非1）

    则继续正常规则  Cm(2)+2*m

代码：