最佳观光组合-LeetCode

1014. 最佳观光组合

🎯 问题描述

描述：
给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分。
两个景点 i 和 j（i < j）组成的观光组合的得分为：

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

即：两个景点的评分之和减去它们之间的距离。
请你返回一对观光景点能取得的最高分。

说明：

• 这是一个线性扫描结合拆分项维护的问题。

• 直接暴力枚举所有 $i, j$ 对需要 $O(N^2)$ 时间。

• 核心优化逻辑：将公式拆分为 $(values[i] + i) + (values[j] - j)$。

• 当我们遍历到 $j$ 时，只需要知道在 $j$ 之前，$(values[i] + i)$ 的最大值是多少。

• 示例：

• 示例 1：

输入：values = [8,1,5,2,6]
输出：11
解释：
- i=0, j=2: values[0] + values[2] + 0 - 2 = 8 + 5 - 2 = 11
- i=0, j=1: 8 + 1 + 0 - 1 = 8
- i=2, j=4: 5 + 6 + 2 - 4 = 9
- 最大值为 11。

💻 解题思路

思路1：一次遍历 + 维护最大值

思路1：代码实现

class Solution:
    def maxScoreSightseeingPair(self, values: List[int]) -> int:
        # rating: 当前组合的得分
        # rate_i: 记录遍历到当前位置之前，(values[i] + i) 的最大值
        # ans: 最终答案
        rating = 0
        rate_i = 0
        ans = 0
        
        # 遍历 j (作为右边的景点)
        for j, rate_j in enumerate(values):
            # 1. 计算以 j 为右端点的最大得分
            # 公式：(values[i] + i) + (values[j] - j)
            # rate_i 就是 (values[i] + i) 的最大值
            # rate_j - j 就是 (values[j] - j)
            rating = rate_i + (rate_j - j)
            
            # 2. 更新全局最大值
            ans = max(ans, rating)
            
            # 3. 更新历史最大值 (values[i] + i)
            # 当前的 j 在未来可能成为 i，所以要更新 rate_i
            rate_i = max(rate_i, rate_j + j)
            
        return ans

思路1：📊 性能分析

• 时间复杂度：$O(N)$
  • 其中 $N$ 是 values 的长度。
  • 只需要遍历数组一次。
• 空间复杂度：$O(1)$
  • 只使用了常数个变量 (rating, rate_i, ans)。

思考

1. 公式拆分（核心技巧）：

   • 原公式：$Score = values[i] + values[j] + i - j$
   • 变形：$Score = (values[i] + i) + (values[j] - j)$
   • 对于固定的 $j$，要使 $Score$ 最大，我们需要在 $i < j$ 的范围内找到最大的 $(values[i] + i)$。

2. 变量含义：

   • rate_i：在代码中，这个变量维护的是当前下标 j 之前所有位置中，$(values[k] + k)$ 的最大值。
   • 虽然变量名叫 rate_i，但它实际上存储的是 $\max_{k < j} (values[k] + k)$。

3. 遍历过程模拟：

   • 当循环进行到 j 时：
     • rate_j 是当前值 values[j]。
     • rate_j - j 是当前作为右端点的贡献值。
     • rate_i 是之前所有点作为左端点的最大贡献值。
     • 两者相加即为以 j 为右端点的最佳组合分。
   • 循环结束前：
     • 我们需要把当前的 j 纳入“历史最大值”的考量，因为对于未来的 j+1 来说，当前的 j 就是一个合法的 i。
     • 所以执行 rate_i = max(rate_i, rate_j + j)。

4. 初始值：

   • rate_i 初始化为 0 是安全的，因为题目中 values 是正整数，且 $i \ge 0$。
   • 实际上，在 $j=0$ 时，由于没有 $i < 0$，rate_i 还没起作用。
   • 在 $j=1$ 时，rate_i 已经被 $j=0$ 更新为 values[0] + 0。