Leetcode 1299. Replace Elements with Greatest Element on Right Side

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

**解析：**Version 1，先排序获取索引，从最大值所在的索引开始遍历，只要是其左侧没有更新过的值都更新，使用left来确定范围，left始终是已更新数据的最右侧，其是下一次遍历的左边界。Version 2从倒数第二个元素开始向前遍历，maximum用来保存右侧最大值，每次遍历先更新当前索引结果位置的数值为maximum，然后更新maximum。

• Version 1

class Solution:def replaceElements(self, arr: List[int]) -> List[int]:n = len(arr)result = [-1] * nindexes = sorted(range(n), key=lambda i: arr[i], reverse=True)left = 0for i in range(n):index = indexes[i]for j in range(left, index):result[j] = arr[index]left = max(left, index)return result

• Version 2

class Solution:def replaceElements(self, arr: List[int]) -> List[int]:n = len(arr)result = [-1] * nmaximum = arr[-1]i = n - 2while i > -1:result[i] = maximummaximum = max(maximum, arr[i])i -= 1return result

Reference

1. https://leetcode.com/problems/replace-elements-with-greatest-element-on-right-side/