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

题目大意:

最佳观光组合

给定正整数数组 AA[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-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。