Medium

题目描述

给你一个长度为 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 <= 10^5
  • 1 <= nums[i] <= 10^5
  • 可以证明，从每个下标 i 出发，最优解是跳到最近的下标 j > i，使得 nums[j] > nums[i]。

解题思路

这是一个贪心算法问题。关键观察是：从任意位置 i 出发，最优策略是跳到下一个更大值的位置。

核心思路：

  1. 贪心策略：从当前位置 i，应该跳到最近的位置 j（j > i），使得 nums[j] > nums[i]。这是因为：

    • 如果中间存在位置 k（i < k < j），且 nums[k] <= nums[i]，那么从 i 直接跳到 j 比先跳到 k 再跳到 j 更优
    • 得分公式 (j-i) * nums[i] 中，nums[i] 固定时，距离越远得分越高

  2. 算法实现：

    • 维护当前最大值和对应位置
    • 遍历数组，当遇到更大值时，计算从上一个最大值位置跳到当前位置的得分
    • 更新最大值和位置

  3. 时间复杂度优化：由于我们总是跳到下一个更大的值，每个位置最多被访问一次，所以可以用一次遍历解决。

推荐解法：贪心算法，时间复杂度 O(n)，空间复杂度 O(1)。

代码实现

class Solution {
public:
    long long findMaximumScore(vector<int>& nums) {
        int n = nums.size();
        long long score = 0;
        int maxVal = nums[0];
        int maxPos = 0;
        
        for (int i = 1; i < n; i++) {
            if (nums[i] > maxVal) {
                score += (long long)(i - maxPos) * maxVal;
                maxVal = nums[i];
                maxPos = i;
            }
        }
        
        // 从最后一个最大值位置跳到末尾
        score += (long long)(n - 1 - maxPos) * maxVal;
        
        return score;
    }
};

class Solution:
    def findMaximumScore(self, nums: List[int]) -> int:
        n = len(nums)
        score = 0
        max_val = nums[0]
        max_pos = 0
        
        for i in range(1, n):
            if nums[i] > max_val:
                score += (i - max_pos) * max_val
                max_val = nums[i]
                max_pos = i
        
        # 从最后一个最大值位置跳到末尾
        score += (n - 1 - max_pos) * max_val
        
        return score

public class Solution {
    public long FindMaximumScore(IList<int> nums) {
        int n = nums.Count;
        long score = 0;
        int maxVal = nums[0];
        int maxPos = 0;
        
        for (int i = 1; i < n; i++) {
            if (nums[i] > maxVal) {
                score += (long)(i - maxPos) * maxVal;
                maxVal = nums[i];
                maxPos = i;
            }
        }
        
        // 从最后一个最大值位置跳到末尾
        score += (long)(n - 1 - maxPos) * maxVal;
        
        return score;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaximumScore = function(nums) {
    const n = nums.length;
    let score = 0;
    let maxVal = nums[0];
    let maxPos = 0;
    
    for (let i = 1; i < n; i++) {
        if (nums[i] > maxVal) {
            score += (i - maxPos) * maxVal;
            maxVal = nums[i];
            maxPos = i;
        }
    }
    
    // 从最后一个最大值位置跳到末尾
    score += (n - 1 - maxPos) * maxVal;
    
    return score;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O(n)只需遍历数组一次
空间复杂度O(1)只使用常量额外空间