Leetcode 79 最佳观光组合

1 题目

1014. 最佳观光组合

给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的 距离 为 j - i。

一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离。

返回一对观光景点能取得的最高分。

示例 1：

输入：values = [8,1,5,2,6]
输出：11
解释：i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11

示例 2：

输入：values = [1,2]
输出：2

2 代码实现

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int best = values[0]; 
        int ans = 0;

        for (int j = 1 ; j < values.size() ; j++){
            ans = max (ans, best + values[j] - j  );

            best = max(best , values[j] + j );
        }

        return ans;
    }
};

题解

思路一句话版

把公式

values[i] + values[j] + i - j

拆成

(values[i] + i) + (values[j] - j)

遍历 j 的时候，只需要维护 j 左边最大的 values[i] + i。

C++ 代码（推荐写法）

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int best = values[0];  // 当前最大的 values[i] + i
        int ans = 0;

        for (int j = 1; j < values.size(); j++) {
            // 用当前 best 和 j 计算得分
            ans = max(ans, best + values[j] - j);

            // 更新 best，供后面的 j 使用
            best = max(best, values[j] + j);
        }

        return ans;
    }
};

为什么是 O(n)？

• 每个元素只遍历一次

• 只用了两个变量

• 时间复杂度：O(n)

• 空间复杂度：O(1)

再帮你对比一下暴力解法（为什么不行）

暴力写法（会超时）

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        ans = max(ans, values[i] + values[j] + i - j);
    }
}

• 时间复杂度：O(n²)

• n 最大到 5 万，直接炸 💥

记忆口诀（刷题用）

i 在左，j 在右
i 的最大值提前存
j 来了直接算

详解这段代码中循环里计算得分和更新best的逻辑

首先，我们先明确这道题的核心公式：对于观光配对(i, j)（要求i < j），得分是values[i] + values[j] + i - j。我们可以把这个公式拆分成两部分：

• 第一部分：values[i] + i（只和i有关）
• 第二部分：values[j] - j（只和j有关）

所以得分就等价于(values[i] + i) + (values[j] - j)（i < j）。

代码逻辑逐行解释

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int best = values[0];  // 初始化为 values[0] + 0（因为i=0时，values[i]+i就是values[0]+0）
        int ans = 0;

        for (int j = 1; j < values.size(); j++) {
            // 第一步：用当前找到的最优i（对应best=values[i]+i）和当前j计算得分
            // 得分 = (values[i]+i) + (values[j]-j) = best + values[j] - j
            ans = max(ans, best + values[j] - j);

            // 第二步：更新best，把当前j当作新的i候选（因为后面的j' > j，此时j就是i）
            // 新的候选值是 values[j] + j，和原来的best比，保留更大的那个
            best = max(best, values[j] + j);
        }

        return ans;
    }
};

举个例子帮你理解

假设values = [8,1,5,2,6]，我们一步步走一遍：

1. 初始化：best = 8 + 0 = 8，ans = 0
2. j=1（values[j]=1）：
   • 得分：8 + 1 - 1 = 8 → ans = 8
   • 更新 best：max(8, 1+1=2) → best=8
3. j=2（values[j]=5）：
   • 得分：8 + 5 - 2 = 11 → ans = 11
   • 更新 best：max(8, 5+2=7) → best=8
4. j=3（values[j]=2）：
   • 得分：8 + 2 - 3 = 7 → ans 还是 11
   • 更新 best：max(8, 2+3=5) → best=8
5. j=4（values[j]=6）：
   • 得分：8 + 6 - 4 = 10 → ans 还是 11
   • 更新 best：max(8, 6+4=10) → best=10
6. 最终返回ans=11（对应 i=0，j=2 的配对，得分 8+5+0-2=11，和计算结果一致）

总结

1. 公式拆分是核心：将原得分公式values[i]+values[j]+i-j拆分为(values[i]+i) + (values[j]-j)，把双变量问题转化为单变量的遍历问题。
2. 贪心维护最优值：遍历j时，用best维护之前所有i < j中values[i]+i的最大值，这样每一步只需要 O (1) 计算，整体时间复杂度是 O (n)。
3. 遍历顺序：因为要求i < j，所以从j=1开始遍历，先计算当前j的得分，再更新best（避免 j 自己和自己配对）。