Medium

题目描述

我们定义数组 arr 的转换数组 conver 如下：

conver[i] = arr[i] + max(arr[0..i])，其中 max(arr[0..i]) 是 arr[j] 在 0 <= j <= i 范围内的最大值。

我们还定义数组 arr 的分数为其转换数组的所有值的和。

给定一个长度为 n 的 0 索引整数数组 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 <= 10^5
  • 1 <= nums[i] <= 10^9

解题思路

解题思路

这道题的关键是理解题意和找到递推关系。

首先分析转换数组的定义：对于位置 i，conver[i] = nums[i] + max(nums[0..i])，即当前元素加上到当前位置为止的最大值。

题目要求的是每个前缀的分数，即转换数组的前缀和。我们可以发现一个重要的递推关系：

核心观察：

  • 设 ans[i] 为前缀 nums[0..i] 的分数
  • 设 prefixMax[i] 为前缀 nums[0..i] 的最大值
  • 则 ans[i] = ans[i-1] + nums[i] + prefixMax[i]

算法步骤：

  1. 维护前缀最大值 prefixMax
  2. 维护前缀分数 prefixScore
  3. 对于每个位置 i：
    • 更新前缀最大值
    • 计算当前位置的转换值：nums[i] + prefixMax
    • 累加到前缀分数中

这种方法避免了重复计算，时间复杂度为 O(n)，空间复杂度为 O(1)（不计算结果数组）。

通过一次遍历就能得到所有前缀的分数，是最优解法。

代码实现

class Solution {
public:
    vector<long long> findPrefixScore(vector<int>& nums) {
        int n = nums.size();
        vector<long long> result(n);
        
        long long prefixScore = 0;
        int prefixMax = 0;
        
        for (int i = 0; i < n; i++) {
            prefixMax = max(prefixMax, nums[i]);
            prefixScore += nums[i] + prefixMax;
            result[i] = prefixScore;
        }
        
        return result;
    }
};

class Solution:
    def findPrefixScore(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = []
        
        prefix_score = 0
        prefix_max = 0
        
        for num in nums:
            prefix_max = max(prefix_max, num)
            prefix_score += num + prefix_max
            result.append(prefix_score)
        
        return result

public class Solution {
    public long[] FindPrefixScore(int[] nums) {
        int n = nums.Length;
        long[] result = new long[n];
        
        long prefixScore = 0;
        int prefixMax = 0;
        
        for (int i = 0; i < n; i++) {
            prefixMax = Math.Max(prefixMax, nums[i]);
            prefixScore += nums[i] + prefixMax;
            result[i] = prefixScore;
        }
        
        return result;
    }
}

var findPrefixScore = function(nums) {
    const n = nums.length;
    const result = new Array(n);
    
    let prefixScore = 0;
    let prefixMax = 0;
    
    for (let i = 0; i < n; i++) {
        prefixMax = Math.max(prefixMax, nums[i]);
        prefixScore += nums[i] + prefixMax;
        result[i] = prefixScore;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)只需要遍历数组一次
空间复杂度O(1)除了结果数组外，只使用常数额外空间

相关题目