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

2021-03-30 HGNULB 约 10 分钟

文章信息 7 个分类 1 个标签

分类

题目描述

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

题意分析

给一个整数数组 arr，要求把每个位置 i 的值替换成 arr[i+1..n-1] 中的最大值；最后一个位置右侧什么都没有，规定替换成 -1。返回替换后的数组。

先把「右侧」这个词钉死：严格右侧，不含自己。位置 i 的新值只由下标大于 i 的元素决定，arr[i] 本身不参与自己的答案。这是本题唯一的语义点，读错就变成了后缀最大值含自身，[17,18,5,4,6,1] 会得到 [18,18,6,6,6,1] 而不是正确的 [18,6,6,6,1,-1]。

其次，题目定义的是同一个下标位置的新值依赖它右边的旧值。也就是说所有的替换在概念上是同时发生的，用的都是原始数组。这直接决定了：如果想原地修改，就必须保证「某个位置被覆盖之前，它的原值已经被用完」。

约束是 $1 \le n \le 10^4$，$1 \le arr[i] \le 10^5$。两点值得注意：数组非空，所以不必处理长度为 0；元素全为正数，所以哨兵值 -1 天然小于任何真实元素，不会被误当成某个位置的最大值。

最后看返回形式：题目要的是整个数组，而不是某个统计量。这类「输出与输入等长、每个位置由某一侧的聚合值决定」的题，天然适合一趟定向扫描。

边界：n = 1 时结果只有 [-1]；数组严格递增时每个位置的答案都是它右边紧邻的那个数；数组严格递减时除最后一位外所有答案都等于 arr[1]。

解法：从右向左维护最大值

核心思路

暴力做法是对每个 i 都往右扫一遍求最大值，$O(n^2)$。$n = 10^4$ 时约 $10^8$ 次比较，卡着时限，而且做了大量重复劳动：求 i 的答案时扫过的那一段，求 i-1 的答案时又要几乎原样再扫一遍。

瓶颈是重复计算后缀最大值。观察相邻两个位置的答案之间的关系：位置 i 的答案是 max(arr[i+1..n-1])，位置 i-1 的答案是 max(arr[i..n-1])，后者恰好等于 max(arr[i], 前者)。也就是说从右往左推进时，答案可以由上一个答案和一个元素在 $O(1)$ 时间内递推出来，完全不需要重新扫描。

于是定义一个滚动状态 rightMax：在处理下标 i 的那一刻，rightMax 表示 arr[i+1..n-1] 这一段（原始值）的最大值；当 i == n-1 时这一段为空，按题意约定其最大值为 -1。

循环不变量就是这句话：每次进入循环体时，rightMax 恰好等于原数组中下标严格大于 i 的所有元素的最大值。初始化 rightMax = -1 让 i = n-1 时的不变量成立；循环体先把 rightMax 写进 arr[i]（这正是位置 i 的答案），再用 arr[i] 的原值更新 rightMax，使不变量在 i 减一后依然成立。

这里出现了一个必须处理的冲突：写答案和更新状态都要碰 arr[i]，而写答案会把原值冲掉。解决办法是在写入前用一个临时变量 cur 把原值扣下来。这一步是全题的技术核心——原地修改的题几乎都绕不开「先保存被覆盖的值」。

顺带说明为什么初值取 -1 而不是某个负无穷：一方面 -1 就是题目为最后一位规定的答案，直接用它作初值等于把边界情况融进了主循环，不需要写 arr[n-1] = -1 的特判；另一方面题目保证元素都是正数，-1 严格小于所有元素，作为「空集的最大值」在语义上也是安全的。

解题步骤

初始化 rightMax = -1：它同时承担两个角色——「空后缀的最大值」和「最后一个位置的答案」。取 -1 而不是 Integer.MIN_VALUE，是因为题目明确规定了最后一位填 -1。

从 i = n - 1 倒着遍历到 i = 0：方向必须是从右往左。递推关系 新答案 = max(当前元素, 旧答案) 只在这个方向上成立；从左往右扫时，位置 i 需要的信息全在它后面，还没被访问到。

暂存原值 cur = arr[i]：下一行就要覆盖 arr[i]，而这个原值还要参与 rightMax 的更新。这一行必须排在写入之前，顺序不可调换。

写入答案 arr[i] = rightMax：此刻 rightMax 正是 arr[i+1..n-1] 的最大值，直接就是位置 i 的答案。注意写的是当前的 rightMax，而不是更新之后的。

更新状态 if (cur > rightMax) rightMax = cur：把刚刚离开的元素并入后缀。这一步必须排在写入之后——先更新再写入，就会把 arr[i] 自己也算进它自己的答案里。

返回 arr：题目允许原地修改，直接返回被改写的输入数组即可，不需要额外开空间。

以 arr = [17, 18, 5, 4, 6, 1] 走一遍，n = 6，初始 rightMax = -1。

i = 5：cur = 1；写入 arr[5] = -1（右侧为空）；1 > -1，rightMax 变为 1。数组现为 [17,18,5,4,6,-1]。

i = 4：cur = 6；写入 arr[4] = 1（右侧只有 1）；6 > 1，rightMax 变为 6。数组现为 [17,18,5,4,1,-1]。

i = 3：cur = 4；写入 arr[3] = 6（右侧 [6,1] 的最大值）；4 > 6 不成立，rightMax 保持 6。数组现为 [17,18,5,6,1,-1]。

i = 2：cur = 5；写入 arr[2] = 6（右侧 [4,6,1]）；5 > 6 不成立，rightMax 仍为 6。数组现为 [17,18,6,6,1,-1]。

i = 1：cur = 18；写入 arr[1] = 6（右侧 [5,4,6,1]）；18 > 6，rightMax 变为 18。数组现为 [17,6,6,6,1,-1]。

i = 0：cur = 17；写入 arr[0] = 18（右侧 [18,5,4,6,1]）；17 > 18 不成立，rightMax 仍为 18。数组现为 [18,6,6,6,1,-1]。

循环结束，返回 [18, 6, 6, 6, 1, -1]，与预期一致。

若漏掉 cur = arr[i] 这一步、直接用 arr[i] 去更新 rightMax：在 i = 1 时 arr[1] 已被写成 6，rightMax 会被更新成 max(6, 6) = 6 而不是 18，于是 arr[0] 得到 6 而不是 18，结果变成 [6, 6, 6, 6, 1, -1]。这是本题最经典的一处错误。

代码实现

class Solution {
    public int[] replaceElements(int[] arr) {
        // 最后一个位置右侧为空，答案固定为 -1，用它当初值可省掉特判。
        int rightMax = -1;
        for (int i = arr.length - 1; i >= 0; i--) {
            // 先存原值：写入答案会覆盖它，而它还要参与后续的最大值更新。
            int cur = arr[i];
            arr[i] = rightMax;
            if (cur > rightMax) {
                rightMax = cur;
            }
        }

        return arr;
    }
}

func replaceElements(arr []int) []int {
    // 最后一个位置右侧为空，答案固定为 -1，用它当初值可省掉特判。
    rightMax := -1
    for i := len(arr) - 1; i >= 0; i-- {
        // 先存原值：写入答案会覆盖它，而它还要参与后续的最大值更新。
        cur := arr[i]
        arr[i] = rightMax
        if cur > rightMax {
            rightMax = cur
        }
    }

    return arr
}

复杂度分析

时间复杂度：$O(n)$。单层循环从右扫到左，每个下标恰好被访问一次，循环体里只有一次赋值和一次比较，都是常数操作。相比暴力的 $O(n^2)$，省下的正是被反复重算的后缀最大值。

空间复杂度：$O(1)$。只额外用了 rightMax 和 cur 两个整型变量，与 n 无关。答案写回入参数组，不申请新数组——如果题目不允许原地修改，则需要 $O(n)$ 的输出空间，但那属于输出本身而非算法的额外开销。

关键点总结

扫描方向由依赖方向决定。答案依赖右边的信息，就从右往左扫；依赖左边就从左往右。看到「每个位置由某一侧的聚合值决定」，第一件事是确定依赖方向，第二件事才是想维护什么状态。

把「重算」改写成「递推」是从 $O(n^2)$ 降到 $O(n)$ 的通用手段。判断能否递推的标准是：相邻两个答案之间是否存在 $O(1)$ 的关系。本题的关系是 max(arr[i..]) = max(arr[i], max(arr[i+1..]))，最大值的这种结合性是它能滚动的根本原因。

原地修改必须先保存被覆盖的值。凡是同一个存储单元既要被写入又要被读取的场景，都要问一句「读和写谁在前」，答案是先读后写，中间用临时变量过渡。

写答案与更新状态的顺序，编码的正是「不含自身」这个语义。先写后更 ⟹ 严格右侧；先更后写 ⟹ 含自身。一行代码的位置就决定了题意对不对。

让哨兵初值同时承担边界答案，可以把特判融进主循环。这里 -1 既是「空后缀的最大值」也是最后一位的规定答案，于是完全不需要为 i = n-1 单独写分支。这是好实现的标志。

面试视角：这题本身几行代码就能写完，面试官真正想听的是循环不变量。开口就把「进入循环体时 rightMax 等于严格右侧的最大值」说清楚，再点明 cur 暂存是为了解决读写冲突，比默默写完代码更有说服力。如果被追问「不许改原数组怎么办」，答：开一个等长的结果数组，同样倒序填写，空间从 $O(1)$ 变成 $O(n)$，时间不变。

易错点总结

错误写法：先更新 rightMax 再写 arr[i] → 把自己算进了自己的答案。对 [17,18,5,4,6,1]，i = 5 时 rightMax 先变成 1，arr[5] 被写成 1 而不是 -1，整体输出 [18,18,6,6,6,1]。

错误写法：不暂存原值，直接 arr[i] = rightMax; rightMax = Math.max(rightMax, arr[i]); → 第二行读到的是刚写进去的新值，rightMax 永远不再增长。对 [17,18,5,4,6,1] 输出 [6,6,6,6,1,-1]，18 完全丢失。

错误写法：从左往右遍历 → 位置 0 需要的信息在它右边，此时一个都还没读过。无论怎么维护状态，arr[0] 只能拿到 -1，输出 [-1, 17, 18, 18, 18, 18] 之类的完全错误结果。

错误写法：rightMax 初值取 0 或 Integer.MIN_VALUE → 取 0 时最后一位会被写成 0 而不是 -1；取 MIN_VALUE 时最后一位是一个巨大的负数，两者都直接违反题目对最后一位的规定。

错误写法：循环写成 for (int i = n - 1; i > 0; i--) → 少处理了下标 0，对 [17,18,5,4,6,1] 输出 [17,6,6,6,1,-1]，第一位仍是原值 17 而不是 18。

错误写法：循环写成 for (int i = n - 2; i >= 0; i--) 却忘了先给 arr[n-1] 赋 -1 → 最后一位保留原值 1，输出 [18,6,6,6,1,1]；这正是「用 -1 当初值」能规避掉的坑。

错误写法：另开数组却仍写 res[i] = max(arr[i], rightMax) → 虽然避开了原地覆盖问题，但把当前元素算进了自己的答案，对 [17,18,5,4,6,1] 得到 [18,18,6,6,6,1]。

错误写法：更新条件写成 if (cur >= rightMax) → 结果不会错（相等时赋值等于没变），但反映出没想清楚「更新的是最大值」，遇到需要区分严格大小的变体题（比如统计右侧严格更大的元素个数）就会出问题。

错误写法：用后缀最大值数组预处理却把边界写成 suffix[n-1] = arr[n-1] → 后缀最大值含自身，arr[n-1] 的答案会取到自己；正确的做法是让 suffix[i] 表示 arr[i+1..] 的最大值，即长度开成 n+1 并令 suffix[n] = -1。

错误写法：以为要返回新数组而没有把 arr 返回，或返回了 null → 题目要求返回替换后的数组本身，原地修改后必须把 arr 交回去。

相似题目

题目	难度	考察点
238. 除了自身以外数组的乘积	中等	左右两侧的前缀积各扫一趟，同样靠「不含自身」的错位来避免除法
42. 接雨水	困难	每个位置要同时用到左最大和右最大，本题是它的单侧简化版，可用双指针进一步省空间
739. 每日温度	中等	求的是右侧第一个更大元素的距离，最大值不再具备结合性，必须换成单调栈
496. 下一个更大元素 I	简单	同样倒序扫描，但状态从一个标量升级成单调栈，因为要的是「第一个更大」而非「最大」
1475. 商品折扣后的最终价格	简单	找右侧第一个不大于当前值的元素，倒序 + 单调栈，可与本题对照体会何时够用标量
121. 买卖股票的最佳时机	简单	正序滚动维护「左侧最小值」，与本题是镜像结构，同样用一个标量完成 $O(1)$ 空间
503. 下一个更大元素 II	中等	在环形数组上找右侧更大元素，靠遍历两遍下标取模处理绕回，倒序思路依然适用