(一)题目描述
给你一个数组 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 |