力扣(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
目录
相关文章
|
1月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
35 1
|
1月前
【LeetCode 27】347.前k个高频元素
【LeetCode 27】347.前k个高频元素
33 0
|
13天前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
1月前
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
24 2
|
1月前
|
程序员 C语言
【C语言】LeetCode(力扣)上经典题目
【C语言】LeetCode(力扣)上经典题目
|
1月前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
78 0
|
1月前
力扣(LeetCode)数据结构练习题(2)
力扣(LeetCode)数据结构练习题(2)
29 0
|
1月前
|
存储
力扣(LeetCode)数据结构练习题
力扣(LeetCode)数据结构练习题
52 0
|
1月前
【LeetCode 06】203.移除链表元素
【LeetCode 06】203.移除链表元素
29 0
|
28天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。