做货代的有哪些网站,北京装修大概多少钱一平方,视频网站点击链接怎么做,接口网站开发文章目录 前言一、题目要求二、算法设计及代码实现2.1 算法思想2.2 代码实现 前言
本文是【程序员代码面试指南#xff08;第二版#xff09;学习笔记】C#版算法实现系列之一#xff0c;用C#实现了《程序员代码面试指南》#xff08;第二版#xff09;栈和队列中的可见的… 文章目录 前言一、题目要求二、算法设计及代码实现2.1 算法思想2.2 代码实现 前言
本文是【程序员代码面试指南第二版学习笔记】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;StackRecord 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;
}
