【每日一题】Leetcode 1299. 将每个元素替换为右侧最大元素
简单
数组
逆序遍历
给你一个数组 arr ，请你将每个元素用它右边最大的元素替换，如果是最后一个元素，用 -1 替换。
完成所有替换操作后，请你返回这个数组。
示例 1：
输入：arr = [17,18,5,4,6,1] 输出：[18,6,6,6,1,-1] 解释： - 下标 0 的元素 --> 右侧最大元素是下标 1 的元素 (18) - 下标 1 的元素 --> 右侧最大元素是下标 4 的元素 (6) - 下标 2 的元素 --> 右侧最大元素是下标 4 的元素 (6) - 下标 3 的元素 --> 右侧最大元素是下标 4 的元素 (6) - 下标 4 的元素 --> 右侧最大元素是下标 5 的元素 (1) - 下标 5 的元素 --> 右侧没有其他元素，替换为 -1
示例 2：
输入：arr = [400] 输出：[-1] 解释：下标 0 的元素右侧没有其他元素。
提示：
1 <= arr.length <= 10^4 1 <= arr[i] <= 10^5
** 注意：该题 arr 中的元素全部大于0，如果存在小于0的值，则初始化 ans 时的末尾元素不能为 -1
思路 1：（逆序遍历 时间复杂度\(O(n)\)）
- 对于数组 arr 中的每个元素 arr[i]，都替换为 max(arr[i+1], arr[i+2], ..., arr[n-1])，同时 arr[n-1] = -1；
- 假设 ans 为最终序列，那么逆序观察:
ans[n-2] = arr[n-1],
ans[n-3] = max(arr[n-2], arr[n-1]),
ans[n-4] = max(arr[n-3], arr[n-2], arr[n-1])，
ans[n-5] = max(arr[n-4], arr[n-3], arr[n-2], arr[n-1])
...
所以通过归纳，可以得出：
ans[n-2] = arr[n-1],
ans[n-3] = max(ans[n-2], arr[n-2]),
ans[n-4] = max(ans[n-3], arr[n-3]),
ans[n-5] = max(ans[n-4], arr[n-4])
...
ans[i] = max(ans[i+1], arr[i+1]) - 那么创建初始 ans 为 [0, 0, ..., 0, -1]，通过逆序遍历 arr ，并设 ans[i] = max(ans[i+1], arr[i+1]) 得到第 i 位的ans。
思路代码 1：（逆序遍历 时间复杂度\(O(n)\)）
class Solution:
def replaceElements(self, arr: List[int]) -> List[int]:
n = len(arr)
ans = [0] * (n - 1) + [-1]
for i in range(n - 2, -1, -1):
ans[i] = max(ans[i + 1], arr[i + 1])
return ans
思路 2：（正序遍历，时间复杂度\(O(n)\) ~ \(O(n^2)\)）
- 如果单纯使用两层 for 嵌套循环将会超时；
- 查找从当前位置 cur 起，cur 后续列表的最大值 max_num 及其所在位置 cur_max；
- 更新 cur 位置为其右侧最大值的位置 cur_max ，并更新 cur 到 cur_max 之间的值为最大值 max_num
- 这样的时间复杂度：
最差为\(O(n^2)\)，例如：[5,4,3,2,1]
最优为\(O(n)\)，例如：[5,1,2,3,4]
代码 2：（正序遍历，时间复杂度\(O(n)\) ~ \(O(n^2)\)）
class Solution:
def replaceElements(self, arr: List[int]) -> List[int]:
ans = []
cur = 0
while cur < len(arr)-1:
max_num = -1
cur_max = 0
for right in range(cur+1, len(arr)):
if arr[right] >= max_num:
max_num = arr[right]
cur_max = right
for i in range(cur_max - cur):
ans.append(max_num)
cur = cur_max
return ans + [-1]
感谢浏览，欢迎关注祁彧w博客！
文章评论