当前位置：首页 > article >正文

力扣LeetCode: 1299 将每个元素替换为右侧最大元素

article 2025/2/23 18:34:38

题目：

给你一个数组 arr ，请你将每个元素用它右边最大的元素替换，如果是最后一个元素，用 -1 替换。

完成所有替换操作后，请你返回这个数组。

示例 1：

输入：arr = [17,18,5,4,6,1]
输出：[18,6,6,6,1,-1]
解释：
- 下标 0 的元素 --> 右侧最大元素是下标 1 的元素 (18)
- 下标 1 的元素 --> 右侧最大元素是下标 4 的元素 (6)
- 下标 2 的元素 --> 右侧最大元素是下标 4 的元素 (6)
- 下标 3 的元素 --> 右侧最大元素是下标 4 的元素 (6)
- 下标 4 的元素 --> 右侧最大元素是下标 5 的元素 (1)
- 下标 5 的元素 --> 右侧没有其他元素，替换为 -1

示例 2：

输入：arr = [400]
输出：[-1]
解释：下标 0 的元素右侧没有其他元素。

提示：

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

解法：倒序遍历

class Solution {
public:
    vector<int> replaceElements(vector<int>& arr) {
        int n = arr.size();
        vector<int> ans(n, 0);
        ans[n-1] = -1;
        int maxNum = 0;
        for(int i = n-2; i >= 0; i--)
        { 
            maxNum = max(arr[i+1], maxNum);
            ans[i] = maxNum;
        }
        return ans;
    }
};

代码逻辑

初始化：
- n 是数组 arr 的长度。
- ans 是一个大小为 n 的数组，用于存储结果。初始时，所有元素都设置为 0。
- ans[n-1] 被设置为 -1，因为最后一个元素右边没有其他元素。
从右向左遍历：
- 从倒数第二个元素开始（即 i = n-2），向左遍历数组。
- maxNum 用于记录当前元素右边所有元素的最大值。
- 在每次迭代中，maxNum 被更新为当前元素右边元素的最大值（即 max(arr[i+1], maxNum)）。
- 然后将 maxNum 赋值给 ans[i]，表示将当前元素替换为它右边所有元素的最大值。
返回结果：
- 最终返回 ans 数组。

示例

假设输入数组为 [17, 18, 5, 4, 6, 1]，函数的执行过程如下：

初始化 ans 为 [0, 0, 0, 0, 0, -1]。
从右向左遍历：
- i = 4：maxNum = max(1, 0) = 1，ans[4] = 1。
- i = 3：maxNum = max(6, 1) = 6，ans[3] = 6。
- i = 2：maxNum = max(4, 6) = 6，ans[2] = 6。
- i = 1：maxNum = max(5, 6) = 6，ans[1] = 6。
- i = 0：maxNum = max(18, 6) = 18，ans[0] = 18。
最终 ans 为 [18, 6, 6, 6, 1, -1]。