• 一个不含有负数的数组可以代表一圈环形山，每个位置的值代表山的高度。比如， {3,1,2,4,5}、{4,5,3,1,2}或{1,2,4,5,3}都代表同样结构的环形山。 山峰A和山峰B能够相互看见的条件为: 1.如果A和B是同一座山，认为不能相互看见。 2.如果A和B是不同的山，并且在环中相邻，认为可以相互看见。 3.如果A和B是不同的山，并且在环中不相邻，假设两座山高度的最小值为min。
  1)如果A通过顺时针方向到B的途中没有高度比min大的山峰，认为A和B可以相互 看见
  2)如果A通过逆时针方向到B的途中没有高度比min大的山峰，认为A和B可以相互 看见
  3)两个方向只要有一个能看见，就算A和B可以相互看见 给定一个不含有负数且没有重复值的数组 arr，请返回有多少对山峰能够相互看见。
  进阶: 给定一个不含有负数但可能含有重复值的数组arr，返回有多少对山峰能够相互看见。

/**
 * 一个不含有负数的数组可以代表一圈环形山，每个位置的值代表山的高度。比如， {3,1,2,4,5}、
 * {4,5,3,1,2}或{1,2,4,5,3}都代表同样结构的环形山。 山峰A和山峰B能够相互看见的条件为:
 * 1.如果A和B是同一座山，认为不能相互看见。 2.如果A和B是不同的山，并且在环中相邻，认为可以相互看见。
 * 3.如果A和B是不同的山，并且在环中不相邻，假设两座山高度的最小值为min。
 * 1)如果A通过顺时针方向到B的途中没有高度比min大的山峰，认为A和B可以相互 看见
 * 2)如果A通过逆时针方向到B的途中没有高度比min大的山峰，认为A和B可以相互 看见
 * 3)两个方向只要有一个能看见，就算A和B可以相互看见 给定一个不含有负数且没有重复值的数组 arr，
 * 请返回有多少对山峰能够相互看见。
 * 进阶: 给定一个不含有负数但可能含有重复值的数组arr，返回有多少对山峰能够相互看见。
 */
public class LookNum {


    // 数组中无重复数字，用公式即可
    public static int lookNum01(int[] arr){
        if(arr == null || arr.length == 0 || arr.length == 1){
            return 0;
        }
        // 2*n - 3
        return (arr.length << 1) - 3;
    }

    // 数组中可能有重复数字
    // 利用单调栈来解
    public static int loolNum02(int[] arr){
        if(arr == null || arr.length == 0 || arr.length == 1){
            return 0;
        }
        int n = arr.length;
        // 先找到数组中的最大下标

        int maxIndex = 0;
        for (int i = 0; i < n; i++) {
            maxIndex = arr[i] > arr[maxIndex] ? i : maxIndex;
        }

        int res = 0;
        Stack<Info> stack = new Stack<>();
        stack.push(new Info(arr[maxIndex]));
        int index = nextIndex(maxIndex,n);
        // 只要没有回到起点就一直遍历
        while (index != maxIndex){
            // 如果当前待加入栈的元素比栈顶元素大，那么结算栈顶元素的可见山峰个数
            while (stack.peek().value < arr[index]){
                int k = stack.pop().times;
                res += getNum(k) + 2 * k;
            }
            if(stack.peek().value == arr[index]){
                stack.peek().times++;
            }else{
                stack.push(new Info(arr[index]));
            }
            index = nextIndex(index,n);
        }

        while (stack.size() > 2){
            int k = stack.pop().times;
            res += getNum(k) + 2 * k;
        }

        if(stack.size() == 2){
            int k = stack.pop().times;
            res += stack.peek().times <= 1 ? getNum(k) + k : getNum(k) + 2*k;
        }

        res += getNum(stack.pop().times);
        return res;
    }

    // 根据k的实效计算内部可见山峰
    private static int getNum(int k){
        return k < 2 ? 0 :k*(k-1)/2;
    }


    // 给点当前下标，和数组长度，返回环形数组中的逆时针下标
    private static int nextIndex(int index,int len){
        int nextIndex = 0;
        nextIndex = index < len - 1  ? index + 1: 0;
        return nextIndex;
    }


    static class Info{
        int value;
        int times;
        public Info(int value){
            this.value = value;
            this.times = 1;
        }
    }

}