18 Replace Elements with Greatest Element on Right Side

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

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 

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;
    }
}