左 . 进阶算法---单调栈
单调栈:
问题描述:给定一个数组 请确定每个元素左右距离最近的比它大的数字
常规想法: 到某一个元素时 通过两个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
代码: