数组中每个数右边第一个比它大的元素

数组中每个数右边第一个比它大的元素

如数组A=[1,5,3,6,4,8,9,10] 输出[5, 6, 6, 8, 8, 9, 10, -1]
如数组A=[8, 2, 5, 4, 3, 9, 7, 2, 5] 输出[9, 5, 9, 9, 9, -1, -1, 5, -1]

## 1、暴力遍历

复杂度为O(n^2)的解法，遍历数组中的每一个后面所有元素，找到第一个大于它的，输出即可
    public static int[] findMaxRight(int[] array) {
        if(array == null)
            return array;
        int size = array.length;
        int[] result = new int[size];
        for (int i = 0; i < size - 1; i++) {
            for (int j = i+1; j < size; j++) {
                if(array[j] > array[i]) {
                    result[i] = array[j];
                    break;
                }
            }
        }
        result[size-1] = -1;//最后元素没有右边元素
        return result;
    }

## 2、借助栈，时间复杂度O(n)
public static int[] findMaxRight(int[] array) {
        if(array == null)
            return array;
        int size = array.length;
        int[] result = new int[size];
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        int index = 1;
        while(index < size) {
            if(!stack.isEmpty() && array[index] > array[stack.peek()]) {
                result[stack.pop()] = array[index];
            }else {
                stack.push(index);
                index++;
            }
        }
        if(!stack.isEmpty())
            result[stack.pop()] = -1;
        return result;
    }