CTF of Z2BNS
0%

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

发表于 分类于 ，
| 阅读次数： |
Valine：
本文字数： 867 阅读时长 ≈ 1 分钟

题目地址

难度：⭐

题目描述：

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

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

示例：

1
2
输入：arr = [17,18,5,4,6,1]
输出：[18,6,6,6,1,-1]

提示：

  • 1 <= arr.length <= 10^4
  • 1 <= arr[i] <= 10^5
🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️解题过程🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️
解题过程：

思路：

直接模拟，遍历数组，对每一个元素找到它右边最大元素并替换，最后一个用-1替换。

c++代码：(执行用时1664ms，击败5.05%，内存消耗14.1M，击败16.20%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> replaceElements(vector<int>& arr) {
        //遍历数组中的元素
        for(int i=0;i<arr.size()-1;++i){
            //找到右边最大的元素
            int tmp=0;
            for(int j=i+1;j<arr.size();++j){
                if(arr[j]>tmp){
                    tmp=arr[j];
                }
            }
            //用右边最大元素替换当前元素
            arr[i]=tmp;
        }
        //最后一个元素用-1替换
        arr[arr.size()-1]=-1;
        return arr;
    }
};
💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎官 方 题 解💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎
官方题解:

方法一：逆序遍历

思路与算法

本题等价于对于数组 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])
来递推地得到答案。

c++代码：(执行用时32ms，击败62.78%，内存消耗14.2M，击败15.02%）

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    vector<int> replaceElements(vector<int>& arr) {
        int n = arr.size();
        vector<int> ans(n);
        ans[n - 1] = -1;
        for (int i = n - 2; i >= 0; --i) {
            ans[i] = max(ans[i + 1], arr[i + 1]);
        }
        return ans;
    }
};

  • 复杂度分析

    时间复杂度：$O(N)$，其中 $N$ 是数组 $arr$ 的长度。

    空间复杂度：$O(1)$，除了存储答案的数组 $ans$ 之外，额外的空间复杂度是 $O(1)$。

⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：

我的解法太暴力了🤣，效率太低。官方题解逆序遍历这个思路真妙,厉害。

------------- THE END! THANKS! -------------