题解 | #数据分析#

第一步，设置维护两个数组 leftBiggerId[]、 rightBiggerId[]，返回结果为res[]

计算 leftBiggerId[i] ：在第i个元素的左边，找到一个最近的元素numbers[x]，使得numbers[x]>numbers[i]，则leftBiggerId[i]=x
计算 rightBiggerId[i] ：在第i个元素的右边，找到一个最近的元素numbers[y]，使得numbers[y]>numbers[i]，则rightBiggerId[i]=y
注意：数组中存在重复元素，因此判断条件为>， 非>=
初始化 res[i]: res[]中的每个元素初始化为Integer.MAX_VALUE

第二步，遍历numbers[]数组，初步计算res[length]的值

numbers[i]为[leftBiggerId[i]+1, rightBiggerId[i]-1]的最大值，该区间长度为length，
所以 res[length-1] = Math.min(res[length-1], numbers[i])

第三步，从尾到头遍历res[], 完成res[]数组的最终计算

初步计算难免会产生以下两个错误：
1、遗漏计算一些长度为length的res[length-1]的数值，
2、res[length-1]的计算结果大于最终结果。
又因为，res[i]的结果必然小于等于res[i+1]，推理如下：
如果当前res[i]>res[i+1]，说明在长度为i+2的数组存在最大值为res[i+1], 那将该长为i+2的数组拆分为两个i+1的数组，则两个i+1长度的数组中必然也有一个最大值为res[i+1]
所以，需要从尾到头遍历res[]数组，res[i] = Math.min(res[i], res[i+1])

    public int[] getMinimums (int[] numbers) {
        int[] leftBiggerId = new int[numbers.length], rightBiggerId = new int[numbers.length];
        leftBiggerId[0] = -1;
        for(int i=1; i<numbers.length; i++){
            if(numbers[i]<numbers[i-1]) leftBiggerId[i] = i-1;
            else{
                int id = leftBiggerId[i-1];
                while(id>=0 && numbers[id]<=numbers[i]) id = leftBiggerId[id];
                leftBiggerId[i] = id;
            }
        }
        rightBiggerId[numbers.length-1] = numbers.length;
        for(int i=numbers.length-2; i>=0; i--){
            if(numbers[i]<numbers[i+1]) rightBiggerId[i] = i+1;
            else{
                int id = rightBiggerId[i+1];
                while(id<numbers.length && numbers[id] <= numbers[i]) id = rightBiggerId[id];
                rightBiggerId[i] = id;
            }
        }
        int[] res = new int[numbers.length];
        for(int i=0; i<numbers.length; i++) res[i] = Integer.MAX_VALUE;
        for(int i=0; i<numbers.length; i++){
            int length = rightBiggerId[i] - leftBiggerId[i] - 1;
            res[length-1] = Math.min(res[length-1], numbers[i]);
        }
        for(int i=numbers.length-2; i>=0; i--)
            res[i] = Math.min(res[i], res[i+1]);
        return res;
    }