很难)"/>
单调栈应用——网易原题——哪两座山的烽火可以相互看见(很难)
给出这样一座环形山,哪两座山的烽火可以相互看见呢?
必须满足如下两个标准:
1.如果两座山相邻,相邻必定能相互看见。
1既可以顺时针也可逆时针走到4。如果两座山峰不相邻,那么必然有两条路。
这两条路中,如果某一条路上出现了所有的值,比1和4的最小值 都不大,则1和4可以相互看见。
比如1到4两条路,都存在比1大的值,所以1和4之间的烽火互相看不见。
2.如果两座山不相邻,则两座山 之间有两条路,
如果某一条路上出现了所有的值,比两座山中的最小值 都不大,则互相看不见
问题:给出这样一个数组,能相互看见烽火的山峰有多少对。
要是数组中所有数都不相等,则答案为:
证明:
首先,不能出现重复的情况,如
所以,我们的目标是让小数找大数。大数不去找小数。
假设一个环中,数目在3个或3个数 以上。
如果我们找到了最高和次高。
然后找到了中间任意的一个数,
假设x,y是 比i还要大的数
那么x、y之后的数,都会被x、y挡住,
所以,红色这一坨,是 i 绝对看不到的
我们假设有n个点
减去最高和次高两个点
剩余n-2个点
一定存在两条,共2*(n-2);
还有最高和次高 这一条
所以,共计 2*n-3;
得证!
但是万一有相同值的情况出现呢?!这是难点!
用单调栈!
先找到全局最大值
若是有多个最大值,找其中一个就行(一般找第一个)
然后开始遍历。
比如下面,
从5开始,往后遍历,然后遍历到3 3
然后准备一个单调栈,
下图表示,当前这个栈中放的是5,有一个5。
所以1不代表下标,就代表有几个
若下一个数是4,则
下面又遇到了一个5,则4要弹出
这时,保存4的信息,包括:4下方的数 和 使4弹出的数
4下方的数 表示 在顺时针方向上,离4最近的,比4大的数。
使4弹出的数,表示 逆时针方向上,离4最近的,比4大的数。
弹出4,压入5后。
一直进行到这个地方,
这4个4会产生多少个山峰,等同于
这4个4相互都可以看到,
产生如下这么多
且 对于每一个4来说,都能看到两边的5,
总之,当4个4 被结算时,共产生如下这么多对
假设对于这样一个栈,当5重新进入时,弹出3时生成的对数 如下所示。
4出来的时候,产生这么多对
我们在遍历过程中,因为一个数的出现 导致 让一个数 从栈中出来 我们是可以正确结算的
但是最后 栈中还有东西的时候,还得继续结算。
比如,对于下面这个数组,
没有一个数结算出来。
我们可以进一步将其抽象为这个样子:
01.58.28
对于3,底下有两条纪录。
结论:最后 栈中还有东西的时候,
当栈中还剩三个或三个以上时,还是可以用下面这个公式。
但是 倒数第二个就有点不同了,如下所示:
对于6个4来说,左右两边一定存在 比其更大的数。(因为有两个5)
所以这种情况下,还是
但若是6个4 下面只有1个5,
相当于 左边和右边都只有1个5
此时表达式应该为:
如果栈下面最后一个数,是3个5呢
还是下面这个公式:
注意这种特殊的情况,
每个4内部是C,4和5之间是k
代码如下:
遍历数组,如果之前找到最大值的位置 arr[maxindex]<arr[i],那maxindex=i。
对于下面这个next index函数,表示在一个环形数组中,i 的下一个位置是啥。
如果 i 小于最后的位置,那么i 位置的下一个就是 i+1
如果 i 已经到达 最后的位置,那么i 位置的下一个回到0。
找到了最大值:
找到了max-index 的下一个
准备一个栈
pair表示当前值是多少,出现的次数多少
类似于:
把最大值扔入栈中:
如果index最后遍历回到max-index,则说明遍历结束。
拿到当前值,开始玩单调栈。
当没法维持栈中 从大到小的顺序,
结算 弹出的数的 山峰对 数量。
CN2 实现:
如果n=1,则有0对。
否则,后面就是CN2
如果当前栈顶的值和现在的值相等,那么将 栈顶的次数+1
否则,将其压入 栈
并建立一个pair
然后,nextpair建立下一个 index
总结:这一块代码非常重要。
下面看单独结算过程中的代码:
栈里面先弹出 times
内部会产生山峰对 getInternalSum
我们之前讲过,如果不是 栈中的倒数第一或者倒数第二,则山峰对一定是下式
如果是 栈中的倒数第一或者倒数第二
则看最后一个数的 数量 是大于1还是1
比如这种情况,4的山峰对是:
如果最后一个数的 数量 大于1
则是下式:
左神扣了1h3min做出来的!
面试,根据通过的 testcase 个数来确定得分
更多推荐
单调栈应用——网易原题——哪两座山的烽火可以相互看见(很难)
发布评论