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;
        //先在環(huán)中找到其中一個最大值的位置，哪一個都行
        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);
        //用“小找大”的方式統(tǒng)計所有可見山峰對
        int res = 0;
        //遍歷開始，當(dāng)index再次回到maxIndex的時候，說明轉(zhuǎn)了一圈，遍歷結(jié)束
        while(index != maxIndex){
            //當(dāng)前數(shù)字arr[index]要進站，判斷是否能滿足棧頂?shù)綏５滓来芜f增
            //若能，則壓入棧；若不能，則彈出棧頂記錄，并計算山峰對數(shù)量
            while(stack.peek().value < arr[index]){
                int k = stack.pop().times;
                //彈出記錄為（x,k),如果k == 1,產(chǎn)生兩對；如果k > 1,產(chǎn)生 2*k+C(2,k)對
                res += getInternalSum(k) + 2 * k;
            }
            //當(dāng)前數(shù)字arr[index]要進棧，若和棧頂數(shù)字一樣，就合并；否則將記錄（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;
    }

    //環(huán)形數(shù)組當(dāng)前位置為i,數(shù)組長度為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);
    }
}