LeetCode 1014. 最佳观光组合

约 3 分钟
文章信息 2 个分类 2 个标签
分类
LeetCode 中等
标签
数组 动态规划

题目描述

✅ 1014. 最佳观光组合

题意分析

从评分数组中选择两个不同景点 i < j，最大化 values[i] + values[j] + i - j。得分既取决于评分，也扣除两点距离，不能只挑评分最高的两个景点。数组至少有两个元素，必须返回一个实际组合的得分。

解法：拆式后维护左侧最大贡献

核心思路

[!blue]

把得分拆成 (values[i] + i) + (values[j] - j)。固定右端点 j 后，第二项已经确定，左侧哪一点最好只取决于 values[i] + i，与当前 j 的具体值无关。因此无需逐个重扫左侧，只需保存这个表达式的历史最大值。

每轮开始时，bestLeft 表示所有 0 <= i < j 中最大的 values[i] + i。用 bestLeft + values[j] - j 就能得到以 j 为右端点的最高得分，再与全局 answer 比较。所有合法组合都有一个右端点，依次处理每个 j 就不会漏掉最优组合。

必须先计算当前组合，再把 values[j] + j 加入左侧候选。这样当前点只能在下一轮及以后作为左端点，始终满足 i < j；如果反过来更新，会允许同一点和自己配对。初始只把第 0 个点放入 bestLeft，从 j = 1 开始，正好建立这个不变条件。

解题步骤

  1. 用第一个点初始化 bestLeft，从 j=1 开始。
  2. 用 bestLeft+values[j]-j 更新答案。
  3. 再更新 bestLeft=max(bestLeft,values[j]+j)。
  4. 扫描结束后返回答案。Java 用最小整数初始化等待首个合法组合更新，Go 直接用前两个点的得分初始化；长度为 2 时，两者都会得到唯一组合。

代码实现

class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        int bestLeft = values[0];
        int answer = Integer.MIN_VALUE;

        for (int j = 1; j < values.length; j++) {
            answer = Math.max(answer, bestLeft + values[j] - j);
            bestLeft = Math.max(bestLeft, values[j] + j);
        }

        return answer;
    }
}

func maxScoreSightseeingPair(values []int) int {
    bestLeft := values[0]
    answer := values[0] + values[1] - 1
    for j := 1; j < len(values); j++ {
        answer = max(answer, bestLeft+values[j]-j)
        bestLeft = max(bestLeft, values[j]+j)
    }
    return answer
}

复杂度分析

  • 时间复杂度：$O(n)$，每个右端点只做常数次比较与计算。
  • 空间复杂度：额外空间 $O(1)$，历史左侧候选被压缩为一个最大值。

关键点总结

[!green]

枚举一个端点后，另一端能否压缩成一个历史最优量，是双层枚举降为单次扫描的关键。

易错点总结

[!yellow]

  • 先更新 bestLeft 会允许 i=j，违反两个景点必须不同的要求。
  • 不能仅选评分最高的两个点，距离项也影响答案。

相似题目

题目 难度 关联与区别
121. 买卖股票的最佳时机 简单 同样枚举较晚端点并维护历史最优；股票题维护最低买入价，本题维护 values[i]+i 的最大值。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/13173311
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！