categories: [Blog,Algorithm]

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

给你一个数组 arr ，请你将每个元素用它右边最大的元素替换，如果是最后一个元素，用 -1 替换。
完成所有替换操作后，请你返回这个数组。
示例 1：
输入：arr = [17,18,5,4,6,1]
输出：[18,6,6,6,1,-1]

  1. class Solution {
  2.     public int[] replaceElements(int[] arr) {
  3.         int   length=arr.length;
  4.         int[] max=new int[arr.length];
  5.         max[length-1]= -1;
  6.         for(int i=length-2;i>=0;i--){
  7.             max[i]=Math.max(max[i+1],arr[i+1]);
  8.         }
  9.         return max;
  10.     }
  11. }

解析

逆序遍历
本题等价于对于数组 arr 中的每个元素 arr[i]，将其替换成 arr[i + 1], arr[i + 2], …, arr[n - 1] 中的最大值。因此我们可以逆序地遍历整个数组，同时维护从数组右端到当前位置所有元素的最大值。

设 ans[i] = max(arr[i + 1], arr[i + 2], …, arr[n - 1])，那么在进行逆序遍历时，我们可以直接通过

ans[i] = max(ans[i + 1], arr[i + 1])

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/replace-elements-with-greatest-element-on-right-side/solution/jiang-mei-ge-yuan-su-ti-huan-wei-you-ce-zui-da-y-5/