算法-19可见的山峰对数量(单调栈)
2022/7/5 1:20:07
本文主要是介绍算法-19可见的山峰对数量(单调栈),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
描述
一个不含有负数的数组可以代表一圈环形山,每个位置的值代表山的高度。比如,{3,1,2,4,5},{4,5,3,1,2}或{1,2,4,5,3}都代表同样结构的环形山。3->1->2->4->5->3 方向叫作 next 方向(逆时针),3->5->4->2->1->3 方向叫作 last 方向(顺时针)。 山峰 A 和 山峰 B 能够相互看见的条件为: 1. 如果 A 和 B 是同一座山,认为不能相互看见。 2. 如果 A 和 B 是不同的山,并且在环中相邻,认为可以相互看见。 3. 如果 A 和 B 是不同的山,并且在环中不相邻,假设两座山高度的最小值为 min。如果 A 通过 next 方向到 B 的途中没有高度比 min 大的山峰,或者 A 通过 last 方向到 B 的途中没有高度比 min 大的山峰,认为 A 和 B 可以相互看见。 问题如下: 给定一个含有负数可能有重复值的数组 arr,请问有多少对山峰能够相互看见?输入描述:
第一行给出一个整数 n,表示山峰的数量。以下一行 n 个整数表示各个山峰的高度。
输出描述:
输出一行表示答案。示例1
输入: 5 3 1 2 4 5 输出: 7
思路
两个阶段:
1. 遍历阶段:
首先找到一个最大值进行存储,然后按照next方向遍历,不断压栈,如果某个记录(X,K)从栈中弹出了,产生可见山峰对的数量为:
2. 清算阶段:
单独清算栈中记录的阶段,分为三个小阶段
第1个小阶段:弹出的记录不是栈中最后一个记录,也不是倒数第二个记录,此时产生山峰对为:
第2个小阶段:弹出的记录是栈中倒数第二个记录(X,K),需要查看栈中最后一条记录(Y,M),此时产生山峰对为:
第3个小阶段:弹出的记录是栈中倒数第一个记录(X,K),此时产生的山峰对为:
解释:2*K(每个节点会有两个山峰对)和1*K(当位于清算阶段的第2个小阶段时,对外能看见的山峰只有最大山峰,并且只有一个,因此每个节点只有一个山峰对)表示,当前节点对外产生的山峰对; C(2,K)表示当前节点内部产生的山峰对。
代码如下:
import java.util.Scanner; import java.util.Stack; public class Main{ //用从上至下递增的单调栈解决问题,为了遵循小山找大山的原则 public static int getMountNum(int[] arr) { if(arr == null || arr.length < 2) { return 0; } Stack<Record> stack = new Stack<Record>(); int maxIndex = 0; //先在环形山圈中找到一个最大值的位置 for (int i = 0; i < arr.length; i++) { maxIndex = arr[maxIndex] < arr[i] ? i : maxIndex; } //后把此数装入stack中 stack.push(new Record(arr[maxIndex])); //从next方向上开始循环 int nextIndex = nextIndex(maxIndex, arr.length); //记录从小找大需要共多少对可见山峰 int res = 0; //把所有山loop一遍,始终保持从顶到底山高递增 while(nextIndex != maxIndex) { //当准备插入新值时,查看是否比当前栈顶数值大,若大于当前栈顶数值 //pop并记录对数 while(stack.peek().val < arr[nextIndex]) { //表示顶部山峰高度到目前为止出现几次 int k = stack.pop().count; res += k == 1 ? 2 : 2 * k + (k * (k-1) / 2); } if (stack.peek().val == arr[nextIndex]) { stack.peek().count++; } else { stack.push(new Record(arr[nextIndex])); } nextIndex = nextIndex(nextIndex, arr.length); } //继续处理余下stack里的山, 如果stack剩下不止两种山 while(stack.size() > 2) { int k = stack.pop().count; res += k == 1 ? 2 : 2 * k + (k * (k-1) / 2); } //此时只剩两种山 if (stack.size() == 2) { int j = stack.pop().count; int k = stack.peek().count; res += k == 1 ? j + (j * (j-1) / 2) : 2 * j + (j * (j-1) / 2); } //若只剩了一种山,则为最高山 if(!stack.isEmpty()) { int k = stack.pop().count; res += k * (k-1) / 2; } return res; } public static int nextIndex(int i, int size) { return i < (size-1) ? i+1 : 0; } //新建类去承载需要的没做山的高度以及次数 public static class Record { public int count; public int val; public Record (int val){ this.val = val; this.count = 1; } } public static void main (String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = sc.nextInt(); } int result = getMountNum(arr); System.out.println(result); } }
这篇关于算法-19可见的山峰对数量(单调栈)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南