输入: 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); } }