leetcode 1014. Best Sightseeing Pair 解题思路分析

题目大意：

最佳观光组合

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

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

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

示例：

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

提示：

1. 2 <= A.length <= 50000
2. 1 <= A[i] <= 1000

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1014

解题思路：

这道题看起来有些绕，如果想要得到最高分的景点组合，首先两个景点的评分要高，并且他们之间的距离要相对较近，也就是题目给出的公式

A[i] + A[j] + i - j

公式中既有加法又有减法，思考起来肯定没那么容易。因此，我们需要将公式变为好理解的形式：

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

这样公式就变成的两个部分，A[i] + i 和 A[j] – j，再简单一点来思考，下标i和j从抽象角度来看其实没有区别，这道题实际上就是求两个最大值，数组中所有数加上下标的最大值，以及数组中所有数减去下标的最大值，唯一需要注意的便是，减法的那个最大值的下标要在加法最大值之后。

看下实现代码：

public int maxScoreSightseeingPair(int[] A) {
    int maxI = Integer.MIN_VALUE; // a[i] + i 的最大值
    int maxJ = Integer.MIN_VALUE; // a[j] - j 的最大值
    int max = Integer.MIN_VALUE; // maxI + maxJ 的最大值
    // 注意maxI的取值范围是0到A.length - 1
    // maxJ的取值范围是1到A.length
    for (int i = 0; i < A.length - 1; i++) {
        // 更新maxI最大值
        if (A[i] + i > maxI) {
            maxI = A[i] + i;
            // 如果maxI最大值发生了改变，因为maxJ要在maxI的下表之后
            // 所以，之前找到的maxJ作废，重新找最大maxJ
            maxJ = Integer.MIN_VALUE;
        }
        // 因为最大maxJ在maxI坐标之后，因此使用i+1下标表示j坐标
        if (A[i + 1] - (i + 1) > maxJ) {
            maxJ = A[i + 1] - (i + 1);
        }
        // 更新返回结果的最大值
        if (maxI + maxJ > max) {
            max = maxI + maxJ;
        }
    }
    return max;
}

本题算法执行时间为3ms

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1014-best-sightseeing-pair-解题思路分析/