题目
一个不含有负数的数组可以代表一圈环形山，每个位置的值代表山的高度。比如，{3,1,2,4,5}、{4,5,3,1,2}或{1,2,4,3,5}都代表同样结构的环形山。3 → 1 → 2 → 4 → 5 → 3方向叫作next方向(逆时针)，3 → 5 → 4 → 2 → 1 → 3方向叫作last方向(时针)，如图下图所示：
山峰的示意图
山峰A和山峰B能够相互看见的条件为:
1. 如果A和B是同一座山，认为不能相互看见。
2. 如果A和B是不同的山，并且在环中相邻，认为可以相互看见。比如上图中，相邻的山峰对有(1,2)(2,4)(4,5)(3,5)(1,3)。
3. 如果A和B是不同的山，并且在环中不相部，假设两座山高度的最小值为min，如果A通过next方向到B的途中没有高度比min大的山峰，或者A通过last方向到B的途中没有高度比min大的山峰，认为A和B可以相互看见。比上图中，高度为3的山和高度为4的山，两座山的高度最小值为3。3从last方向走向4，中途会遇见5，所以a方向走不通；3从next方向走向4，中途会遇见1和2，但是都不大于两座山高度的最小值3，所以next方向可以走通。有一个能走通就认为可以相互看见。再如，高度为2的山和高度为5的山，两个方向上都走不通，所以不能相互看见。入上图中所有在环中不相邻，并且能看见的山峰对有(2，3)(3，4)。
给定一个不含有负数且没有重复值的数组arr，请返回有多少对山峰能够相互看见。
进阶问题:给定一个不含有负数但可能含有重复值的数组arr，返回有多少对山峰能够相互看见。
要求
如果arr长度为N，没有重复值的情况下的时间复杂度达到O(1)，可能有重复值的情况下的时间复杂度请达到O(N)。
思路
原问题：时间复杂度O(1)的解。如果数组中所有的数字都不一样，可见山峰对的数量可以由简单公式得到。环形结构中只有1座山峰时，可见山峰对的数量为0；环形结构中只有2座山峰时，可见山峰对的数量为1。这都是显面易见的。环形结构中有 i 座山峰时( i＞2)，可见山峰对的数量为 2 * i - 3。下面给出证明。
我们只用高度小的山峰去找高度大的山峰，而永远不用高度大的山峰去找高度小的山峰。比如题目描述中的例子，从 2 出发按 “小找大” 原则，会找到(2,3)和(2,4)，但是不去尝试2能不能看到1，因为这是 “大找小” 而不是 “小找大”。(1,2)这一对可见山峰不会错过，因为从1出发按照 “小找大” 原则找的时候会找到这一对。从每一个位置出发，都按照 “小找大” 原则找到山峰对的数量，就是总的可见山峰对数量。
如果有 i 座山峰并且高度都不一样，必然在环中存在唯一的最大值和唯一的次大值(第二大的值)，如图 '最大值和次最大值的示意图 ' 所示。最大值和次最大值的示意图
图 '最大值和次最大值的示意图 ' 中，X 节点表示除最高值和次高值之外的任何一座山峰，因为 X 既不是最大值，也不是次大值，所以 X 在last方向上必存在第一个高度比它大的节点，假设这个节点是 Y，Y 就有可能是最大值节点，但是一定存在。X 在next方向上必存在第一个高度比它大的节点，假设这个节点是 Z、Z 有可能就是次大值节点，但是一定存在。因为 Y 是 X 在last方向上第一个高度比它大的节点，所以 X 在last方向上没到达 Y 之前遇到的所有山峰高度都小于 X，不符合 “小找大” 方式。同理，X 在next方向上没到达 Z 之前遇到的所有山峰高度都小于 X，不符合 “小找大” 方式。同时根据可见山峰对的定义，Y 从last方向到达这一段的每一个节点 X 都看不见。所以从 X 出发能找到且只能找到(X,Y)和(X,Z)这2对。如果环中有 i 个节点，除了最大值和次大值之外，还剩 i - 2 个节点，这 i - 2 个节点都根据 “小找大” 的方式，每一个都能找到2対，所以一共有( i - 2) * 2 对，还有1对，就是次大值能够看见最大值这对。所以一共是 2 * i - 3对。
进阶问题:时间复杂度O(N)的解。读者在阅读该解法之前，“单调栈结构” 问题的解法。还是按照 “小找大” 的方式来求解可见山峰对个数，下面举例说明，假设环形山如 '例题示意图' 所示例题示意图
首先遍历一次环形山结构，找到最大值的位置，如果最大值不止一个，找哪一个最大值都行。比如图 '例题示意图' 中5是最大值且不止一个，找到哪个都行，我们选择最下方的5。准备一个栈，记为 stack<Record>，stack中放入的是如下数据结构:
public calss Record {
public int value;
public int times;public Record(int velue) {
this.value = value;
this.times = 1;
}
}接下来从最大值开始沿着next方向准备再遍历一遍环形山。 stack中先放入(5,1)，表示5这个高度，收集1个，以后放入记录时，都保证第一维的数字从顶到底是依次增大的。目前stack从项到为：(5,1)。
沿next方向来到5。生成记录(5,1)，发现如果这个记录加入stack，第一维的数字从顶到就不是依次增大的。所以stack弹出(4,3)，这条记录表示当前收集到的这3个4有可能相部或者即便是不相邻，中间夹的数字也一定小于4(比如之前遇到的2)，并且所夹的数字用 “小找大” 的方式算过山峰对了(看看之前遇到的2在弹出的时候)，如 '示意图' 所示
沿next方向来到4，生成记录(4,1)表示4这个数，收集1个，发现如果这个记录加入，stack第一维的数字从顶到底是依次增大的，所以放入(4,1)，目前stack从顶到底依次为: (4,1)、(5,1)。
沿next方向来到3，生成记录(3,1)，表示3这个数，收集1个，发现如果这个记录加入，第一维的数字从顶到底是依次增大的，所以放入(3,1)。目前stack从顶到底依次为: (3,1)、(4,1)、(5,1)。
沿next方向来到5，生成记录(5,1)。发现如果这个记录加入stack，第一维的数字从顶到底就不是依次增大，所以stack开始弹出记录，首先弹出(3,1)，当前来到的数字是5，当前弹出的数字3，原来在栈中的时候当前弹出数字的下面是4，说明当前弹出的3在next方向上遇到第一个大于它的数就是当前来到的数字5，在last方向上遇到第一个大于它的数就是此时的栈顶的4，进一步说明从当前出的3出发，通过 “小找大” 的方式，可以找到2个可见山峰对，就是(3,4)和(3,5)， stack继续弹出记录(4,1)，当前来到的数字是5，当前弹出的数字是4，原来在栈中的时候，当前弹出数字下面数字是5，说明从当前准备弹出的4，通过 “小找大” 的方式，又找到2个可见山峰对 。stack从顶到送底只剩下(5,1)这个记录，当前生成的新记录是(5,1)把两个记录合并，目前stack从顶到底为:(5,)，发现的山峰对数为: 4。
沿next方向来到4，生成记录(4,1)。发现如果这个记录加入stack，第一组的数字从顶到底依次增大的，所以放入(4,1)。目前 stack从顶到次为: (4,1)，(5,2)，发现的山峰对数量: 4。
沿next方向来到2，生成记录(2,1)。发如果这个记录加入stack，第一维的数字从顶到底依次增大的，所以放入(2,1)。日前stack从项到底依次为: (2,1)、(4,1)、(5,2)，发现的山峰对数量: 4。
沿next方向来到 4，生成记录(4,1)。发现如果这个记录加入stack，第一维的数字从顶到底就不是依次增大的了。所以stack开始弹出记录，首先单出(2,1),与上面的解释可理，可以发现2个山峰对。此时stack顶部记录为(4,2)，把两个记录合并。目前stack从顶到底依次为: (4,2)、(5,2)。发现的山峰对数量: 6。
沿next方向来到 4，生成记录(4,1)。此时 stack顶部记录为(4,2)，把两个记录合并。目前 stack从顶到底依次为:(4,3)、(5,2)，发现的山峰对数量: 6
示意图
示意图中虚线表示可能夹住某些数字，但都是比4小的，而且都是算过山峰对的数字，不需要去关心。那么这3个4一共产生多少对可见山峰呢?首先，每一个4都可以看到由last方向上的5和next方向上的5；其次，这3个4内部，每两个4都可以相互看见。所以产生 2 * 3 + C(2,3) ＝ 9对山峰。
总结一下。如果在遍历阶段，某个记录从sack中弹出了，产生可见山峰对的数量为:
1) 如果K == 1，产生2对
2) 如果K > 1，产生 2 * K + C(2,A)对。
stack在弹出(4,3)之后，当前顶部记录为(5,2)，当前生成的记录是(5,1)，合并在一起。目stack从顶到底为: (5,3)，发现的山峰对数量:15。
沿next方向来到3，生成记录(3,1)。发现如果这个记录加入stack，第一指的数字从顶到底是依次增大的，所以放入(3,1)。日前stack从顶到底依次为:(3,1)、(5,3)，发现的山峰对数量: 15。
沿next方向来到2，生成记录(2,1)发现如果这个记录加入stack，第一维的数字从顶到底是依次增大的，所以放入(2,1)，目前stack从到底依次为:(2,1)、(3,1)、(5,3)，发现的山峰对数量：15。
遍历完毕，在遍历过程中发现了15对山峰。进行最后一个阶段: 单独清算中记录的阶段。这个阶段又分成3个小阶段。
第1个小阶段: 弹出的记录不是栈中最后一个记录，也不是倒数第二个记录。
第2个小阶段: 弹出的记录是栈中倒数第二个记录。
第3个小阶段: 弹出的记录是栈中最后一个记录。
比如上面的例子，在最后单独清算中记录的阶段，就是3个小阶段都有，弹出(2,1)时是第1个小阶段，弹出(3,1)时是第2个小阶段，弹出(5,3)时是第3个小阶段。'示意图的上图' 是没有第1小阶段，但是有2、3小阶段的例子。
假设从最下方5开始，沿next方向遍历，遍历完成后，stack从顶到底依次为:(4,2)、(5,1)然后进入清算阶段会发现没有第1小阶段。
'示意图的下图' 是没有第1，2小阶段，但是有第3小阶段的例子
示意图
假设从最下方5开始，沿next方向遍历，遍历完成后，stack从顶到底为:(5,2)，然后进入清算阶段余发现没有第1，2小阶段。
任何环形结构都不可能出现没有第3小阶段的情况，因为我们总是从环形结构的最大值开始遍历的，它既然是整个环形结的最大值，所以不会在遍历阶段的过程中被其他高度的山峰释放，一定会等判清算阶段时才会从栈中弹出。
在最后的清算阶段，假设从栈中弹出的记录为(X,K)，那么产生山峰对的逻辑如下。
1)如果发现当前记录位于第1小阶段，产生山峰对为: 如果K＝1，产生2对; 如果 K＞1，产生2 * K + (2,K) 对，这是因为(X,K)这个记录弹出之后，利下的记大于或等于2条，而整个图形是环，说明这K个X在last方向和next方向一定都能找到大于它们高度的山。
举个例子，比如清算阶段时，stack从顶到底依次为:(2,1)、(3,1)、(5,3)，在(2,1)弹出的时候，栈中还剩(3,1)、(5,3)，说明这个2布日last方向上能遇到3，在next方向上会遇到5(因为是环)，产生2对可见山峰。
再举个例子。比如清算阶段时，stack从顶到底依次为:(1,7)、(2,6)、(3,10)、(5,7)，在(1,7)弹出的时候，栈中还到剩(2,6)、(3,10)、(5,7)。说明这7个1在last方向上能遇到2，在next方向上会遇到5(因为是环)。每个1都能看见last方向上的2和next方向上的5，所以对外一共产生7*2个可见山峰对个1内部产生C(2,7)个可见山峰对。
2) 如果发现当前记录位于第2小阶段，也就是当前记录为栈中倒数第二条记录，那么需要查看中的最后一条记来、假设最后一条记球为(Y,M)。如果M == 1，产生 1 * K+C(2,K)对; 如果M > 1，产生 2 * K+C(2,K)对。
举个例子，比如清算阶段时，stack从顶到底依次为:(4,7)、(5,1)，在(4,7)弹出的时候栈中还剩(5,1)，说明这7个4在last方向上能遇到5，在next方向上也会遇到5，但是遇到的是同一个5(因为是环)。每个4都能看见last方向上的5和next方向上的5，但因为是同一个5所以対外一共产生 1 * 7个可见山峰对，7个4内部产生C(2,7)个可见山峰对。
再举个例子，比如清算阶段时，stack从顶到底依次为:(4,7)、(5,3)。在(4,7)弾出的时候，中还剩(5,3)，说明这7个4在lsat方向上能遇到5, 在next方向上也会遇到5，而且遇到的是不同的5(因为最后一条记录收集到的5不止1个)每个4都能看见last方向上的5和 next方向上的5，但因为是不同的5，所以对外一共产生2 * 7个可见山峰对，7个4内部产生C(2,7)个可见山峰对。
3) 如果发现当前记录位于第3小阶段，也就是当前记录为栈中最后一条记录。这个 X 一定是环中的最大值。根据 “小找大” 的方式，对外不会产生山峰对，只是 K 个 X 内部产生山峰对如果 K == 1，产生0对；如果K>1，产生C(2,K)对。
代码演示
package com.itz.zcy.stackAndQueue;
import java.util.Stack;
/**
* 一个不含有负数的数组可以代表一圈环形山，每个位置的值代表山的高度。比如，{3,1,2,4,5}、{4,5,3,1,2}或{1,2,4,3,5}
* 都代表同样结构的环形山。3 → 1 → 2 → 4 → 5 → 3方向叫作next方向(逆时针)，3 → 5 → 4 → 2 → 1 → 3
* 方向叫作last方向(时针)，
* 山峰A和山峰B能够相互看见的条件为:
* 1. 如果A和B是同一座山，认为不能相互看见。
* 2. 如果A和B是不同的山，并且在环中相邻，认为可以相互看见。比如上图中，相邻的山峰对有(1,2)(2,4)(4,5)(3,5)(1,3)。
* 3. 如果A和B是不同的山，并且在环中不相部，假设两座山高度的最小值为min，如果A通过next方向到B的途中没有高度比min大的山峰，或者A通过last方向到B的途中没有高度比min大的山峰，认为A和B可以相互看见。比上图中，高度为3的山和高度为4的山，两座山的高度最小值为3。3从last方向走向4，中途会遇见5，所以a方向走不通；3从next方向走向4，中途会遇见1和2，但是都不大于两座山高度的最小值3，所以next方向可以走通。有一个能走通就认为可以相互看见。再如，高度为2的山和高度为5的山，两个方向上都走不通，所以不能相互看见。入上图中所有在环中不相邻，并且能看见的山峰对有(2，3)(3，4)。
* 给定一个不含有负数且没有重复值的数组arr，请返回有多少对山峰能够相互看见。
* 进阶问题:给定一个不含有负数但可能含有重复值的数组arr，返回有多少对山峰能够相互看见。
*/
public class VisibleNum {
/**
* 查找并返回可见山峰的数
* @param arr
* @return
*/
public static int getVisibleNum(int [] arr){
// 进行异常判定(判定arr为空，长度小于2的情况)
if (arr == null|arr.length<2){
return 0;
}
int size = arr.length;
int maxIndex = 0;
// 先在循环中找到其中一个最大值，任意一个
for (int i=0;i<size;i++){
maxIndex=arr[maxIndex]<arr[i]?i:maxIndex;
}
Stack<Record> stack = new Stack<>();
// 先把(最大值,1)这个记录放入stack中
stack.push(new Record(arr[maxIndex]));
// 从最大的位置的下一个开始沿next方向遍历
int index = nextIndex(maxIndex,size);
// 用“小找大”的方式统计所有可见的山峰数
int res = 0;
// 遍历阶段开始,当index再次回到maxIndex的时候，说明转一圈，遍历阶段就结束
while (index != maxIndex){
// 当前数字arr[index]要进栈，判断会不会破坏第一维数字从顶到底依次变大
// 如果破坏理了，就依次弹出栈顶记录，并计算山峰数量
while (stack.peek().value<arr[index]){
int k = stack.pop().times;
// 弹出记录(X,K)如果 k==1,产生2对
// 如果k>1,产生2*k+C(2,K)对
res += getInternalSum(k)+2*k;
}
// 当数字arr[index]要进入栈了，如果和当前栈顶的数字一样就合并
// 不一样就把记录(arr[index],1)放入栈中
if (stack.peek().value==arr[index]){
stack.peek().times++;
}else {
stack.push(new Record(arr[index]));
}
index = nextIndex(index,size);
}
// 清算阶段
// 清算阶段的第1阶段
while (stack.size()>2){
int times = stack.pop().times;
res+= getInternalSum(times)+2*times;
}
// 清算阶段的第2阶段
if (stack.size()==2){
int times = stack.pop().times;
res += getInternalSum(times)+(stack.peek().times==1?times:2*times);
}
// 清算阶段的第3阶段
res += getInternalSum(stack.peek().times);
return res;
}
/**
* 如果 k==1,返回0，如果 k>1, 返回C(2,K)
* @param k
* @return
*/
private static int getInternalSum(int k){
return k==1?0:(k*(k-1)/2);
}
/**
* 环形数组种当前位置为i数组长度为size，返回i的下一个位置
* @param i
* @param size
* @return
*/
private static int nextIndex(int i,int size){
return i<(size-1)?(i+1):0;
}
public static void main(String[] args) {
int[] arr = {4,4,2,4,5,3,4,5,2,3,5};
System.out.println(getVisibleNum(arr));
}
}
class Record{
public int value;
public int times;
public Record(int value){
this.value = value;
this.times = 1;
}
}
总结
该题的原问题和单调栈结构” 问题的解法类似。做到时间复杂度可以O(1)，含有重复的时间复杂度为O(N)
文献：左程云著 《程序员代码面试指南IT名企算法与数据结构题目最优解》（第二版）
版权声明：此文版权归作者所有！
