LeetCode 题解工作台
到达数组末尾的最大得分
给你一个长度为 n 的整数数组 nums 。 你的目标是从下标 0 出发，到达下标 n - 1 处。每次你只能移动到 更大 的下标处。 从下标 i 跳到下标 j 的得分为 (j - i) * nums[i] 。 请你返回你到达最后一个下标处能得到的 最大总得分 。 示例 1： 输入： nums = …
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
假设我们从下标 ，跳到下标 ，那么得分为 $(j - i) \times \text{nums}[i]$。这相当于我们走了 $j - i$ 步，每一步都得到了 的得分。然后我们从 继续跳到下一个下标 ，得分为 $(k - j) \times \text{nums}[j]$，以此类推。如果 $nums[i] \gt nums[j]$，那么我们就不应该从 跳到 ，因为这样得到的得分一定比从 直…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个长度为 n 的整数数组 nums 。
你的目标是从下标 0 出发，到达下标 n - 1 处。每次你只能移动到 更大 的下标处。
从下标 i 跳到下标 j 的得分为 (j - i) * nums[i] 。
请你返回你到达最后一个下标处能得到的 最大总得分 。
示例 1：
输入：nums = [1,3,1,5]
输出：7
解释：
一开始跳到下标 1 处，然后跳到最后一个下标处。总得分为 1 * 1 + 2 * 3 = 7 。
示例 2：
输入：nums = [4,3,1,3,2]
输出：16
解释：
直接跳到最后一个下标处。总得分为 4 * 4 = 16 。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 105
解题思路
方法一：贪心
假设我们从下标 ，跳到下标 ，那么得分为 。这相当于我们走了 步，每一步都得到了 的得分。然后我们从 继续跳到下一个下标 ，得分为 ，以此类推。如果 ，那么我们就不应该从 跳到 ，因为这样得到的得分一定比从 直接跳到 得到的得分要少。因此，我们每一次应该跳到下一个比当前下标对应的值更大的下标。
我们可以维护一个变量 ，表示当前为止，我们遇到的最大的 的值。然后我们从左到右遍历数组，直到倒数第二个元素，每次更新 ，并且累加得分。
遍历结束后，我们得到的就是最大的总得分。
时间复杂度 ，其中 为数组 的长度。空间复杂度 。
class Solution:
def findMaximumScore(self, nums: List[int]) -> int:
ans = mx = 0
for x in nums[:-1]:
mx = max(mx, x)
ans += mx
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity can range from O(n^2) for naive evaluation to O(n) with a monotonic queue or optimized approach. Space complexity is O(n) for storing scores or O(1) if using in-place tracking with a pointer strategy. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate attempts all jumps naively without leveraging greedy invariant.
- question_mark
Candidate fails to maintain cumulative maximum score while iterating.
- question_mark
Candidate overlooks distance multiplier in scoring, reducing total score.
常见陷阱
外企场景- error
Forgetting to multiply the jump distance by nums[i], leading to incorrect score.
- error
Selecting a local maximum without considering future cumulative impact.
- error
Inefficiently scanning all indices, causing timeouts on large arrays.
进阶变体
外企场景- arrow_right_alt
Compute maximum score when jumps can skip backward but still maximize total.
- arrow_right_alt
Modify scoring to use sum of nums[i] instead of distance multiplier.
- arrow_right_alt
Restrict jumps to fixed-length steps and find maximum achievable score.