LeetCode 题解工作台
一个数组所有前缀的分数
定义一个数组 arr 的 转换数组 conver 为： conver[i] = arr[i] + max(arr[0..i]) ，其中 max(arr[0..i]) 是满足 0 的所有 arr[j] 中的最大值。 定义一个数组 arr 的 分数 为 arr 转换数组中所有元素的和。 给你一个下标从 …
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 前缀和
答案摘要
我们用变量 记录数组 中前 个元素的最大值，用数组 记录数组 中前 个元素的分数。 接下来，遍历数组 ，对于每个元素 ，我们更新 ，即 $mx = \max(mx, nums[i])$，然后更新 ，如果 $i = 0$，则 $ans[i] = nums[i] + mx$，否则 $ans[i] = nums[i] + mx + ans[i - 1]$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 前缀和 题型思路
题目描述
定义一个数组 arr 的 转换数组 conver 为：
conver[i] = arr[i] + max(arr[0..i])，其中max(arr[0..i])是满足0 <= j <= i的所有arr[j]中的最大值。
定义一个数组 arr 的 分数 为 arr 转换数组中所有元素的和。
给你一个下标从 0 开始长度为 n 的整数数组 nums ，请你返回一个长度为 n 的数组 ans ，其中 ans[i]是前缀 nums[0..i] 的分数。
示例 1：
输入：nums = [2,3,7,5,10] 输出：[4,10,24,36,56] 解释： 对于前缀 [2] ，转换数组为 [4] ，所以分数为 4 。 对于前缀 [2, 3] ，转换数组为 [4, 6] ，所以分数为 10 。 对于前缀 [2, 3, 7] ，转换数组为 [4, 6, 14] ，所以分数为 24 。 对于前缀 [2, 3, 7, 5] ，转换数组为 [4, 6, 14, 12] ，所以分数为 36 。 对于前缀 [2, 3, 7, 5, 10] ，转换数组为 [4, 6, 14, 12, 20] ，所以分数为 56 。
示例 2：
输入：nums = [1,1,2,4,8,16] 输出：[2,4,8,16,32,64] 解释： 对于前缀 [1] ，转换数组为 [2] ，所以分数为 2 。 对于前缀 [1, 1]，转换数组为 [2, 2] ，所以分数为 4 。 对于前缀 [1, 1, 2]，转换数组为 [2, 2, 4] ，所以分数为 8 。 对于前缀 [1, 1, 2, 4]，转换数组为 [2, 2, 4, 8] ，所以分数为 16 。 对于前缀 [1, 1, 2, 4, 8]，转换数组为 [2, 2, 4, 8, 16] ，所以分数为 32 。 对于前缀 [1, 1, 2, 4, 8, 16]，转换数组为 [2, 2, 4, 8, 16, 32] ，所以分数为 64 。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 109
解题思路
方法一：前缀和
我们用变量 记录数组 中前 个元素的最大值，用数组 记录数组 中前 个元素的分数。
接下来，遍历数组 ，对于每个元素 ，我们更新 ，即 ，然后更新 ，如果 ，则 ，否则 。
时间复杂度 ，其中 为数组 的长度。忽略答案数组的空间消耗，空间复杂度 。
class Solution:
def findPrefixScore(self, nums: List[int]) -> List[int]:
n = len(nums)
ans = [0] * n
mx = 0
for i, x in enumerate(nums):
mx = max(mx, x)
ans[i] = x + mx + (0 if i == 0 else ans[i - 1])
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each element is processed once. Space complexity is O(n) for storing the prefix scores array. The solution uses constant extra space beyond the output. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expecting you to track a running maximum rather than recomputing for each prefix.
- question_mark
Looking for O(n) linear time solution instead of nested prefix loops.
- question_mark
Observing if you handle large numbers and long arrays correctly.
常见陷阱
外企场景- error
Recomputing the maximum for every prefix instead of maintaining a running maximum.
- error
Incorrectly summing conversion values, missing doubling or prefix rules.
- error
Failing to handle edge cases where nums has one element or all identical values.
进阶变体
外企场景- arrow_right_alt
Compute the minimum instead of maximum for each prefix and sum conversion values.
- arrow_right_alt
Return only the final total score of the entire array instead of all prefixes.
- arrow_right_alt
Apply a similar conversion logic for a 2D matrix row-wise using prefix maximums.