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


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

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

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

解析

逆序遍历
本题等价于对于数组 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/


文章作者:   future
版权声明:   本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 future !
 上一篇
572. 另一个树的子树 572. 另一个树的子树
572. 另一个树的子树难度简单 451给定两个非空二叉树 s 和 t,检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。示例 1:给定的树 s:
本篇 
1299. 将每个元素替换为右侧最大元素 1299. 将每个元素替换为右侧最大元素
1299. 将每个元素替换为右侧最大元素给你一个数组  arr ,请你将每个元素用它右边最大的元素替换,如果是最后一个元素,用  -1 替换。完成所有替换操作后,请你返回这个数组。示例 1:输入:arr = [17,18,5,4,6,1]输
  目录