【C#算法实现】可见的山峰对数量

前言

本文是【程序员代码面试指南（第二版）学习笔记】C#版算法实现系列之一，用C#实现了《程序员代码面试指南》（第二版）栈和队列中的可见的山峰对数量。文中的示意图也都来自此书。

一、题目要求

给出一个全为正整数的循环数组，每一个数字表示一个山峰的高度，找出一共有几对山峰可以相互看到。
相互看到的条件：如果两座山峰之间不管是顺序看也好逆序看也罢，只要有一个方向可以达到两座山峰之间的山的高度都小于两座山峰的要求，那么就说明相互可以看到。

如图，最下方的5可以和左边的3相互看到，因为中间的2 < 3且2 < 5。最下面的5和最右边的5也是相互可见的，虽然顺时针方向有一个5不小于5，但是逆时针方向中间只有4和3，是满足要求的，所以互相可见。

二、算法设计及代码实现

2.1 算法思想

概述：首先要确定一点，假如A能看到B，那么其实计算过程中如果还计算B能看到A就重复了。而又因为低山峰找高山峰较为方便，这里确定为小找大。确定为小找大后，就可以定义一个单调递增的栈，保证栈内元素始终为栈顶到栈底依次增大。如果遇到相同大小的元素，那么只需要在该元素位置记录次数加一即可。首先将栈底放入最大值，随后遍历数组。遇到不符合单调性的元素入栈时，说明栈顶元素找到了前进方向的比自己高的山了，由于栈底肯定大于栈顶，也就说明栈顶两端都满足小找大的条件了，不可能找到更多对的山峰了，这时就可以出栈计算结果了。遍历结束一遍后，还会有剩余元素，这时依旧按照小找大规则进行出栈计算即可。

详细步骤：
1、定义一个记录值和出现次数的结构体，这里选择用类是因为结构体是值类型，修改不如引用类型方便。
2、初始化一个栈和记录结果的变量。
3、找出最大值和最大值所在的序列作为遍历的起点。
4、循环遍历一遍数组，遍历每个元素都做以下操作：
1）栈空直接放入元素。
2）栈顶小于当前要放入的元素，那么就出栈，出栈累加结果，此时找到的山峰对数为2 * times + times * (times - 1) / 2。
3）如果相等，则直接累加出现次数。
4）符合单调性，则直接放入。
5、遍历结束后还有剩余元素，此时分为三个阶段：
1）如果剩余元素大于等于三个，逐个出栈，直到剩下2个为止。出栈时，累加结果公式为2 * times + times * (times - 1) / 2。
2）倒数第二个元素的出栈：记最后一个元素的重复次数为lt，那么累加结果公式为times * (lt > 1 ? 2 : 1) + times * (times - 1) / 2
3）最后一个元素的出栈公式为times * (times - 1) / 2。

2.2 代码实现

public class Record(int value, int times) {public int value = value;public int times = times;
}public static int GetVisibleNum(int[] arr) {int n = arr.Length;Stack<Record> stack = new();int ans = 0;// 找出最大值和位置int max = 0;int maxIndex = -1;for (int i = 0; i < n; i++) {if (arr[i] > max) {max = arr[i];maxIndex = i;}}// 从最大值的位置开始遍历for (int i = maxIndex; i < n + maxIndex; i++) {int index = i % n;int value = arr[index];// 如果栈为空, 直接入栈if (stack.Count == 0) {stack.Push(new Record(value, 1));continue;}// 栈顶元素小于当前元素, 则出栈while (stack.Peek().value < value) {Record record = stack.Pop();ans += record.times * 2 + record.times * (record.times - 1) / 2;}// 栈顶元素等于当前元素, 则更新栈顶元素的次数if (stack.Peek().value == value) {Record record = stack.Peek();record.times++;}// 栈顶元素大于当前元素, 则入栈else {stack.Push(new Record(value, 1));}}// 栈中剩余元素while (stack.Count > 2) {Record record = stack.Pop();ans += record.times * 2 + record.times * (record.times - 1) / 2;}if (stack.Count == 2) {Record record = stack.Pop();Record last = stack.Peek();ans += record.times * (last.times > 1 ? 2 : 1) + record.times * (record.times - 1) / 2;}if (stack.Count == 1) {Record record = stack.Pop();ans += record.times * (record.times - 1) / 2;}return ans;
}