1014. 最佳观光组合

🟠   🔖  数组 动态规划  🔗 力扣 LeetCode

题目

You are given an integer array values where values[i] represents the value of the ith sightseeing spot. Two sightseeing spots i and j have a distance j - i between them.

The score of a pair (i < j) of sightseeing spots is values[i] + values[j] + i - j: the sum of the values of the sightseeing spots, minus the distance between them.

Return the maximum score of a pair of sightseeing spots.

Example 1:

Input: values = [8,1,5,2,6]

Output: 11

Explanation: i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11

Example 2:

Input: values = [1,2]

Output: 2

Constraints:

• 2 <= values.length <= 5 * 10^4
• 1 <= values[i] <= 1000

题目大意

给你一个正整数数组 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 <= values.length <= 5 * 10^4
• 1 <= values[i] <= 1000

解题思路

在这道题中，我们需要找到两个景点 i 和 j (满足 i < j)，使得得分公式 values[i] + values[j] + i - j 最大。通过分析公式，可以拆分为两部分：

• 左边部分：values[i] + i，固定时只与 i 有关。
• 右边部分：values[j] - j，固定时只与 j 有关。

在遍历 j 时，我们只需记录当前最大值 values[i] + i（称为 maxLeft），并将其与 values[j] - j 进行计算即可。

1. 初始化 maxLeft 为第一个元素的 values[0] + 0，因为 i = 0。
2. 初始化 maxScore 为 0，表示当前最大得分。
3. 从 i = 1 开始遍历数组：
   • 计算当前景点得分为 maxLeft + (values[j] - j)，并更新 maxScore。
   • 更新 maxLeft 为当前的最大值，即 max(maxLeft, values[i] + i)。
4. 遍历完成后，返回 maxScore。

复杂度分析

• 时间复杂度：O(n)，其中 n 是 values 的长度，遍历一次数组 values 即可。
• 空间复杂度：O(1)，只使用了常量变量 maxLeft 和 maxScore。

代码

/**
 * @param {number[]} values
 * @return {number}
 */
var maxScoreSightseeingPair = function (values) {
	const n = values.length;
	let maxLeft = values[0]; // 初始 maxLeft = values[0] + 0
	let maxScore = 0; // 最大得分

	for (let i = 1; i < n; i++) {
		// 计算当前得分，并更新最大得分
		maxScore = Math.max(maxScore, maxLeft + values[i] - i);
		// 更新 maxLeft
		maxLeft = Math.max(maxLeft, values[i] + i);
	}
	return maxScore;
};