1299. 将每个元素替换为右侧最大元素

解法一

先倒序排序并存储排序前的序号。用一个指针指向排序后数组的第一个数，然后开始计算答案数组。
如果当前指向的这个元素的原始下标小于等于当前答案数组元素的下标，说明这个元素原来在左侧，因此指针后移，考虑下一个次大值，否则它就是右侧的最大值。
时间复杂度：, N为数组长度。

import java.util.Arrays;
import java.util.Comparator;
class Solution {
    Comparator<Element> elementComparator = new Comparator<Element>() {
        @Override
        public int compare(Element o1, Element o2) {
            // 按照value的值降序排列
            return (o2.value - o1.value);
        }
    };
    public int[] replaceElements(int[] arr) {
        Element[] elements = new Element[arr.length];
        for (int i = 0; i < arr.length; ++i) {
            elements[i] = new Element(arr[i], i);
        }
        Arrays.sort(elements, elementComparator);
        int[] ans = new int[arr.length];
        ans[arr.length - 1] = -1;
        int ptr = 0;
        for (int i = 0; i < arr.length - 1; ++i) {
            while ((ptr < arr.length) && (elements[ptr].index <= i)) {
                ++ptr;
            }
            ans[i] = elements[ptr].value;
        }
        return ans;
    }
}
class Element {
    // 元素值
    public int value;
    // 元素序号
    public int index;
    public Element(int value, int index) {
        this.value = value;
        this.index = index;
    }
}

解法二

从后向前更新最大值，最后一个数特殊处理。
时间复杂度：, N为数组长度。

class Solution {
    public int[] replaceElements(int[] arr) {
        int[] ans = new int[arr.length];
        ans[arr.length - 1] = arr[arr.length - 1];
        int max = -1;
        for (int i = arr.length - 2; i >= 0; --i) {
            max = Math.max(max, arr[i + 1]);
            ans[i] = max;
        }
        ans[arr.length - 1] = -1;
        return ans;
    }
}