package pers.mao.stackAndQueue.demo_11;

import java.util.Stack;

/**
 * @author Mao Qingbo
 * @date 2021-01-27
 */
public class GetVisibleMountainNum {
    public int getVisibleNum(int [] arr){
        if(arr == null || arr.length < 2){
            return 0;
        }
        int size = arr.length;
        int maxIndex = 0;
        //先在环中找到其中一个最大值的位置，哪一个都行
        for(int i = 0; i < size; i++){
            maxIndex = arr[maxIndex] < arr[i] ? i : maxIndex;
        }
        Stack<Record> stack = new Stack<Record>();
        //先将（最大值，1）这个记录放在stack中
        stack.push(new Record(arr[maxIndex]));
        //从最大值位置的下一个位置开始沿next方向遍历
        int index = nextIndex(maxIndex,size);
        //用“小找大”的方式统计所有可见山峰对
        int res = 0;
        //遍历开始，当index再次回到maxIndex的时候，说明转了一圈，遍历结束
        while(index != maxIndex){
            //当前数字arr[index]要进站，判断是否能满足栈顶到栈底依次递增
            //若能，则压入栈；若不能，则弹出栈顶记录，并计算山峰对数量
            while(stack.peek().value < arr[index]){
                int k = stack.pop().times;
                //弹出记录为（x,k),如果k == 1,产生两对；如果k > 1,产生 2*k+C(2,k)对
                res += getInternalSum(k) + 2 * k;
            }
            //当前数字arr[index]要进栈，若和栈顶数字一样，就合并；否则将记录（arr[index],1)压入栈
            if(stack.peek().value == arr[index]){
                stack.peek().times++;
            }
            else{
                stack.push(new Record(arr[index]));
            }
            index = nextIndex(index,size);
        }
        //清算阶段开始
        //清算阶段的第1小阶段
        while (stack.size() > 2){
            int times = stack.pop().times;
            res += getInternalSum(times) + 2 * times;
        }
        //清算阶段的第2小阶段
        if(stack.size() == 2){
            int times = stack.pop().times;
            res += getInternalSum(times) + times;
        }
        //清算阶段的第3小阶段
        res += getInternalSum(stack.pop().times);
        return res;
    }

    //环形数组当前位置为i,数组长度为size,返回i的下一个位置
    public int nextIndex(int i,int size){
        return i < size -1 ? i+1 : 0;
    }

    //如果k == 1，返回0；否则，返回C(2,k)
    public int getInternalSum(int k){
        return k == 1 ? 0 : (k * (k - 1) / 2);
    }
}