关注 每天一道编程题 专栏，一起学习进步。

题目

Given an array arr, replace every element in that array with the greatest element among the elements to its right, and replace the last element with -1.

After doing so, return the array.

Example 1:

Input: arr = [17,18,5,4,6,1]
Output: [18,6,6,6,1,-1]

Constraints:

1 <= arr.length <= 10^4
1 <= arr[i] <= 10^5

分析

题意：
遍历数组，将当前数字替换成右侧最大的一个数字
最后将末尾的一个数字替换为-1

i=0 17 18 5 4 6 1 ⇒ 18 18 5 4 6 1
i=1 18 18 5 4 6 1 ⇒ 18 6  5 4 6 1
i=2 18 6  5 4 6 1 ⇒ 18 6  6 4 6 1 
i=3 18 6  6 4 6 1 ⇒ 18 6  6 6 6 1 
i=4 18 6  6 6 6 1 ⇒ 18 6  6 6 6 1 
i=5 18 6  6 6 6 1 ⇒ 18 6  6 6 6 -1 

难点：
拿到每个数字时，还得找出其后的最大数，遍历自然能够解决，但是复杂度太高。
下面使用一种嵌套for循环拆成同级的两个for循环的方式

解答

class Solution {
    public int[] replaceElements(int[] arr) {
        
		//创建一个数组专门存放arr[i]之后的最大值
        int[] maxTillNowArr = new int[arr.length];
        
        //初始化最大值
		int curMax = -1;
		
		//从后往前查找，找出arr[i]右边的最大值；这个容易写成从前往后查找，自己想想为什么
        for(int i = arr.length-1; i >= 0; i--)
        {
            curMax = Math.max(curMax, arr[i]);
            maxTillNowArr[i] = curMax;
        }
        
		//将arr[i]替换成右边的最大值
        for(int i = 0; i < arr.length-1; i++)
        {
            arr[i] = maxTillNowArr[i+1];
        }
       
	   // 最后置为 -1
        arr[arr.length-1] = -1;
        
        return arr;
    }
}