烽火相望

【网易原题】给你一个数组，数组中的每个数代表一座山的高度，这个数组代表将数组中的数从头到尾连接而成的环形山脉。比如数组[2,1,3,4,5]形成的环形山脉如下：

其中蓝色的圆圈就代表一座山，圈中的数字代表这座山的高度。现在在每座山的山顶都点燃烽火，假设你处在其中的一个山峰上，要想看到另一座山峰的烽火需满足以下两个条件中的一个：

  • 你想看的山峰在环形路径上与你所在的山峰相邻。比如你在山峰A上，那么你能够看到B和E上的烽火。
  • 如果你想看的山峰和你所在的山峰不相邻，那么你可以沿环形路径顺时针看这座山也可以沿环形路径逆时针看这座山，只要你放眼望去沿途经过的山峰高度小于你所在的山峰和目标山峰，那么也能看到。比如C想看E，那么可以通过C->B->A->E的方式看，也可以通过C->D->E的方式看。前者由于经过的山峰的高度1和2比C的高度3和E的高度5都小，因此能看到；但后者经过的山峰D的高度4大于C的高度3，因此C在通过C->D->E这个方向看E的时候视线就被山峰D给挡住了。

问：所有山峰中，能互相看到烽火的两两山峰的对数。以[2,1,3,4,5]为例，能互相看见的有：2,1,1,3,3,4,4,5,5,2,2,3,3,5，共7对。

此题分一下两种情况

1、数组中无重复的数

这种情况下，答案可以直接通过公式2*N-3可以求得（其中N为数组长度），证明如下：

假设A是在山峰中最高，B在所有山峰中第二高。那么环形路径上介于A和B之间的任意一座山峰（比如K），逆时针方向在到达A之前或到达A时一定会遇到第一座比它高的山峰，记这座山峰和K是一对；顺时针方向，在到达B之前或到达B时，一定会遇到第一个比K高的山峰，记这座山峰和K是一对。也就是说对于除A,B之外的所有山峰，都能找到两对符合标准的，这算下来就是(N-2)*2了，最后AB也算一对，总数是(N-2)*2+1=2N-3。

但如果数组中有重复的数就不能采用上述的方法了

2、数组中可能有重复的数

利用单调栈

首先找出数组中最大数第一次出现的位置，记为M。从这个数开始遍历数组并依次压栈（栈底到栈底从大到小的单调栈），以如下的环形山脉为例：

从M开始压栈，同时附带一个计数器：

当压入5时，违反单调栈约定因此结算4（4左边第一个比它高的是9，右边第一个比它高的是5，因此能和4配对的有两对）；接着再压入5、压入4，重点来了：连续两次再压入4该如何处理：

这是数组中有重复的数时，如何使用单调栈解决此题的关键：如果压入的元素与栈顶元素相同，将栈顶元素的计数器加1，那么再压入两个4之后栈中情况：

然后压入9，导致弹出并结算4。那么如何结算计数器大于1的数据呢？首先，这3座高度相同的山峰两两配对能够组成C(3,2)=3对，此外其中的每座山峰左边离它最近的比它高的是5、右边离它近的比它大的是9，因此这3座山峰每座都能和5、9配对，即3*2=6，因此结算结果为3+6=9……

如果数据压完了，那就从栈顶弹出数据进行结算，直到结算栈底上一个元素之前（栈底元素是最大值），弹出数据的结算逻辑都是C(K,2)+K*2（其中K是该数据的计数器数值）。

倒数第二条数据的结算逻辑有点复杂，如图，以结算4为例：

如果K的数值大于1，那么这6座高度为4的山峰结算逻辑还是上述公式。但如果K为1，那么结算公式就是C(K,2)+K*1了。

最后对于最大值M的结算，假设其计数器的值为K，如果K=1，那么结算结果为0；如果K>1，那么结算结果为C(K,2)。

public static class Pair {
		public int value;
		public int times;

		public Pair(int value) {
			this.value = value;
			this.times = 1;
		}
	}

	public static int comunications(int[] arr) {
		// index of first max value
		int maxIndex = 0;
		for (int i = 0; i < arr.length; i++) {
			maxIndex = arr[maxIndex] < arr[i] ? i : maxIndex;
		}

		int value = arr[maxIndex];
		int index = nextIndex(arr, maxIndex);
		int res = 0;
		
		Stack<Pair> stack = new Stack();
		stack.push(new Pair(value));
		while (index != maxIndex) {
			while (!stack.empty() && value > stack.peek().value) {
				int times = stack.pop().times;
				// res+=getInternalPairs(times)+times;
				// res+=stack.isEmpty()?0:times;
				res += getInternalPairs(times) + times * 2;
			}
			if (!stack.empty() && value == stack.peek().value) {  //当前数和栈顶值相等
				stack.peek().times++;
			} else {
				stack.push(new Pair(value));
			}
			index = nextIndex(arr, index);
		}

		while (!stack.empty()) {
			int times = stack.pop().times;
			res += getInternalPairs(times);
			if (!stack.empty()) {
				res += times;
				if (stack.size() > 1) {
					res += times;
				} else {
					res += stack.peek().times > 1 ? times : 0;
				}
			}
		}
		return res;
	}

	// C(K,2)
	public static int getInternalPairs(int times) {
		return (times * (times - 1)) / 2;
	}

	//下一個位置
	public static int nextIndex(int[] arr, int index) {
		return index < arr.length - 1 ? index + 1 : 0;
	}