/**
1. 先计算数组的度为x
2. 双指针扫描, 先向右扫描到相同度的子数组, 左面收缩到最小, 记录结果
*/

/**
1. 另一种做法是记录所有数字的边界, 找到所有频率最大的数,计算最小值
*/


class Solution {

    public int findShortestSubArray(int[] nums) {
        // return doublePoint(nums);
        return recordBound(nums);
    }

    public int recordBound(int[] nums){
        Map<Integer, Integer> left = new HashMap<>();
        Map<Integer, Integer> right = new HashMap<>();
        Map<Integer, Integer> freq = new TreeMap<>();

        int maxFreq = 1;
        for (int i = 0 ; i < nums.length ; i++){
            int num = nums[i];

            if (!left.containsKey(num)) left.put(num, i);
            right.put(num, i);

            if (!freq.containsKey(num)) freq.put(num, 0);
            freq.put(num, freq.get(num) + 1);
            maxFreq = Math.max(maxFreq, freq.get(num));
        }

        int result = Integer.MAX_VALUE;
        for (Integer key : freq.keySet()){
            if (freq.get(key) == maxFreq){
                result = Math.min(result, right.get(key) - left.get(key) + 1);
            }
        }

        return result;
    }


    public int doublePoint(int[] nums){
        Map<Integer, Integer> degree = new HashMap<>();
        int deg = 0;
        int n = nums.length;
        degree.clear();
        for (int i = 0; i < n ; i++){
            int num = nums[i];
            if (!degree.containsKey(num)) degree.put(num, 0);
            degree.put(num, degree.get(num)+1);
            deg = Math.max(deg, degree.get(num));
        }

        int curDeg = 0;        int curNum = -1;
        degree.clear();
        int resL = -1, resR = -1;
        int i = 0 , j = 0;

        while (i < n || j < n){
            if (curDeg == deg && i < n){
                int num = nums[i++];
                degree.put(num, degree.get(num) - 1);
                if (curNum == num) curDeg--;
                if (j - i < resR - resL || (resR == -1 && resL == -1)){
                    resL = i;
                    resR = j;
                }
            } else if (curDeg < deg && j < n){
                int num = nums[j++];
                if (!degree.containsKey(num)) degree.put(num, 0);
                degree.put(num, degree.get(num)+1);
                if (curNum == -1 || curDeg < degree.get(num)){
                    curNum = num;
                    curDeg = degree.get(num);
                }
            } else {
                break;
            }
        }
        return resR - resL + 1;
    }
}