可见的山峰对数量(进阶)

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main() {
    int n = 0;
    cin >> n;
    if(n == 1){
        cout << 0;
        return 0;
    }

    vector<long> arr(n);
    for(int i =0;i < n;i++){
        cin >> arr[i];
    }
    int maxId = 0;
    for(int i = 1;i < n;i++){
        if(arr[i] > arr[maxId]){
            maxId = i;
        }
    }

    long res = 0;
    stack<pair<long,long>> stk;
    stk.push({arr[maxId],1});
    int p = (maxId + 1) % n;
    while(p != maxId){
        while(!stk.empty() && stk.top().first != arr[p]){
            if(stk.top().first > arr[p]) break;
            long k = stk.top().second;
            res += (2 * k + k * (k-1)/2);
            stk.pop(); 
        }
        if(!stk.empty() && stk.top().first == arr[p]){
            stk.top().second++;
        }else{
            stk.push({arr[p],1});
        }
        p = (p + 1)%n;
    }


    if(stk.size() < 2){
        cout << "false";
        return 0;
    }

    long k = 0;
    
    while (stk.size() >= 3) {
        k = stk.top().second;
        res += (2 * k + k*(k-1)/2);
        stk.pop();    
    }

    k = stk.top().second;
    stk.pop();
    int maxK = stk.top().second;
    if(maxK == 1) res +=(k + k*(k-1)/2);
    else res += (2 * k + k*(k-1)/2 + maxK * (maxK-1)/2);

    cout << res;
}
// 64 位输出请用 printf("%lld")

今天吃【豆沙面包】

let n=parseInt(readline())
let nums=readline().split(' ').map(item=>parseInt(item))

let stack=[]
let max=0,max_index=0
let res=0
const findmax=function(){
    for(let i=0;i<nums.length;i++)
        if(nums[i]>nums[max_index]){
            max= nums[i]
            max_index=i
        }
}

const getFactorial=function(n){

        if(n==1||n==0) return 1
         return getFactorial(n-1)*n


}

const findmountains=function(){
    let index=(max_index+1)%nums.length

    while(index!=max_index){
        if(stack[stack.length-1][0]>nums[index]){
            stack.push([nums[index],1])
            index=(index+1)%nums.length
        }else if(stack[stack.length-1][0]==nums[index]){
            stack[stack.length-1][1]++
            index=(index+1)%nums.length
        }else{
//             不是最后一个
            while(stack[stack.length-1][0]<nums[index]){
               let [curMountain,curNum]=stack.pop()
               res+=curNum>=2?curNum*2+(getFactorial(curNum)/(2*getFactorial(curNum-2))):curNum*2
            }
        }
    }

    while(stack.length){
        let [curMountain,curNum]=stack.pop()
        //只有最大值了
        if(stack.length+1==1){        
            res+=curNum>=2?(getFactorial(curNum)/(2*getFactorial(curNum-2))):0
        }else if(stack.length+1==2){       
            if(stack[0][1]==1){
                res+=curNum>=2?curNum+(getFactorial(curNum)/(2*getFactorial(curNum-2))):curNum
            }else{
                res+=curNum>=2?curNum*2+(getFactorial(curNum)/(2*getFactorial(curNum-2))):curNum*2
            }
        }else{
            res+=curNum>=2?curNum*2+(getFactorial(curNum)/(2*getFactorial(curNum-2))):curNum*2
        }
    }

}

findmax()
stack.push([nums[max_index],1])
findmountains()

console.log(res)

import java.util.*;

public class Main{
    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);
    }
    //用从上至下递增的单调栈解决问题，为了遵循小山找大山的原则
    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;
        }
    }
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static int getVisibleNum(int[] arr) {
        int res = 0;
        if (arr == null || arr.length < 2) {
            return res;
        }
        int size = arr.length;
        int maxIndex = 0;
        // 先在环中找到其中任意一个最大值的位置
        for (int i = 0; i < size; i++) {
            if (arr[i] > arr[maxIndex]) {
                maxIndex = i;
            }
        }
        Stack<int[]> stack = new Stack<>();
        stack.push(new int[] {arr[maxIndex], 1});
        int index = getNextIndex(maxIndex, size);
        int number;
        while (index < maxIndex) {
            while (stack.peek()[0] < arr[index]) {
                number = stack.pop()[1];
                res += number * 2 + getInternalSum(number);
            }
            if (stack.peek()[0] == arr[index]) {
                stack.peek()[1]++;
            } else {
                stack.push(new int[] {arr[index], 1});
            }
            index = getNextIndex(index, size);
        }
        while (stack.size() > 2) {
            number = stack.pop()[1];
            res += number * 2 + getInternalSum(number);
        }
        if (stack.size() == 2) {
            number = stack.pop()[1];
            if (stack.peek()[1] == 1) {
                res += number + getInternalSum(number);
            } else {
                res += number * 2 + getInternalSum(number);
            }
        }
        number = stack.pop()[1];
        return res + getInternalSum(number);
    }

    private static int getNextIndex(int maxIndex, int size) {
        if (maxIndex == size - 1) {
            return 0;
        } else {
            return maxIndex + 1;
        }
    }

    private static int getInternalSum(int k) {
        if (k == 1) {
            return 0;
        } else {
            return k * (k - 1) / 2;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bufferedReader.readLine());
        String[] numbers = bufferedReader.readLine().split(" ");
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(numbers[i]);
        }
        System.out.println(getVisibleNum(arr));
    }
}