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 自己和自己配对）。