ac

问题如下：
给定一个含有负数可能有重复值的数组 arr，请问有多少对山峰能够相互看见

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class Record{
    int val;
    int cnt;

    public Record(int val, int cnt) {
        this.val = val;
        this.cnt = cnt;
    }
}

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));


    static int getNext(int i, int n){
        if(i == n-1){
            return 0;
        }
        return i + 1;
    }

    static int getCn2(int n) {
        if (n == 1) {
            return 0;
        } else {
            return n * (n - 1) / 2;       // C(n,2)
        }
    }

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            int val = sc.nextInt();
            arr[i] = val;
        }
        // 找到其中一个最大值
        int maxIndex = -1;
        int maxVal = Integer.MIN_VALUE;
        for(int i=0;i<n;i++){
            if(arr[i] > maxVal){
                maxVal = arr[i];
                maxIndex = i;
            }
        }
        int res = 0;

        Stack<Record> recordStack = new Stack<>(); // 维持一个递减的栈
        recordStack.push(new Record(maxVal, 1));

        int index = getNext(maxIndex, n);
        while (index != maxIndex){ // next一圈
            // 栈里面小于当前值的pop，计算
            while (!recordStack.isEmpty() && recordStack.peek().val < arr[index]){
                int k = recordStack.pop().cnt;
                res += getCn2(k) + 2 * k;
            }

            if (!recordStack.isEmpty() && recordStack.peek().val == arr[index]){
                recordStack.peek().cnt ++;
            }else {
                recordStack.push(new Record(arr[index], 1));
            }
            index = getNext(index, n);
        }
        // 不是栈中最后一个记录，也不是倒数第二个
        while (recordStack.size() > 2) {
            int k = recordStack.pop().cnt;
            res += getCn2(k) + 2 * k;
        }
        // 是栈中倒数第二个
        while (recordStack.size() == 2) {
            int k = recordStack.pop().cnt;
            if (recordStack.peek().cnt == 1) {
                res += getCn2(k) + k;
            } else {
                res += getCn2(k) + 2 * k;
            }

        }
        // 最后一个记录
        res += getCn2(recordStack.pop().cnt);
        System.out.println(res);
    }

}
/*
5
3 1 2 4 5

7
 */