每日一题20250216-LC1299

2025.2.16 2025.2.16 Algorithm 300 1 分钟

题目信息

题目难度: Easy 掌握程度: 🌟🌟🌟🌟🌟

1299. 将每个元素替换为右侧最大元素 - 力扣（LeetCode）

解题思路

解法 1 ：模拟

遍历位置，从当前位置获取当前位置右边最大值，替换当前值即可

时间复杂度 \(O(n^2)\)

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

解法 2：一次遍历

反向遍历，从数组右边开始遍历，此时我们通过维护一个 pre 变量来标识当前元素右侧最大元素值，进行替换

替换之后，如果当前元素 cur > pre ，那么我们就替换 pre 为当前元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
    public int[] replaceElements(int[] arr) {
        int n = arr.length;
        int pre = arr[n-1];
        for(int i = n - 1 ; i >= 0 ; i--){
            int tmp = arr[i];
            if(i == n-1){
                arr[i] = -1;
            }else{
                arr[i] = pre;
            }
            if(tmp > pre){
                pre = tmp;
            }
        }
        return arr;
    }

作者：dreamkidd
链接：https://dreamkidd.github.io/posts/每日一题20250216-lc1299/