力扣(LeetCode)算法题解:1299. 将每个元素替换为右侧最大元素

简介: 力扣(LeetCode)算法题解:1299. 将每个元素替换为右侧最大元素

(一)题目描述

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

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

来源:力扣(LeetCode

链接:https://leetcode-cn.com/problems/reverse-words-in-a-string-iii

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

(二)输入、输出示例

示例 1:

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

(三)代码实现

方法1(php版):

解题思路

1.既然需要找到每个元素右侧的最大值,肯定需要遍历1次。

2.如果正序来查找,那判断你右侧最大值的时候也需要遍历n-1次。那就是o(n²)的时间复杂度

3.本题技巧在于从后往前查找。默认max是最大值,从后往前遍历,判断每个元素是否比最大值大,如果是则交换;若否则继续遍历。

4.顺带考察了如果交换两个数的值。

代码实现

class Solution {
    /**
     * @param Integer[] $arr
     * @return Integer[]
     */
    function replaceElements($arr) {
        $max = -1;
        for ($k = count($arr)-1; $k >=0 ; $k--){
            $temp = $arr[$k];
            $arr[$k] = $max; // 将右侧的最大值赋值给当前元素
            if($temp > $max){
              // 更新最大值
                $max = $temp;
            }
        }
        return $arr;
    }
}

(四)性能分析

运行时间 内存消耗
8ms 14.8 MB
目录
相关文章
|
15天前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
30 1
|
21天前
【LeetCode 27】347.前k个高频元素
【LeetCode 27】347.前k个高频元素
29 0
|
27天前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
37 0
|
14天前
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
20 2
|
24天前
|
算法
【链表】算法题(二) ----- 力扣/牛客
【链表】算法题(二) ----- 力扣/牛客
|
22天前
【LeetCode 06】203.移除链表元素
【LeetCode 06】203.移除链表元素
27 0
|
22天前
【LeetCode-每日一题】移除元素
【LeetCode-每日一题】移除元素
29 0
|
24天前
|
算法
【链表】算法题(一) ----- 力扣 / 牛客
【链表】算法题(一) ----- 力扣 / 牛客
|
24天前
|
算法
【顺序表】算法题 --- 力扣
【顺序表】算法题 --- 力扣