每日题解:LeetCode 1014. 最佳观光组合

Author Avatar
清水雅然君 06月 17,2020

题目地址

题目描述

给定正整数数组 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
 

提示:

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

解法

JAVA

class Solution {
    public int maxScoreSightseeingPair(int[] A) {
  int len=A.length;
        int ans=0;int max=A[0]+0;
        //A[i] + A[j] + i - j  ==》 A[i]+i  A[j]-j
        for (int i = 1; i < len; i++) {
            ans=Math.max(ans,max+A[i]-i);
            max=Math.max(max,A[i]+i);
        }
       return ans;
    }
}

解题思路

遍历

根据题目的计算i,j景点观光组合得分为A[i] + A[j] + i - j,如果得到最大的得分,那就需要类似冒泡排序的做法,遍历两次数组,每次计算得分,然后通过函数Math.max()获得最大的得分值获取最大值,时间复杂度为O(n^2),但是没法通过测试用例。
对于每一个景点,其A[j] - j是固定不变的,所以,我们要想办法扩大 A[i]+i的值,所以,我们可以在遍历数组时,可以维护一个最大A[i]+i值,然后再维护一个观光组合得分的最大值。

int ans=0;int max=A[0]+0;
 //A[i] + A[j] + i - j  ==》 A[i]+i  A[j]-j
for (int i = 1; i < len; i++) {
//计算最大景点观光组合得分
ans=Math.max(ans,max+A[i]-i);
//需要一个A[i]+i值
max=Math.max(max,A[i]+i);
 }

这题目关键点在修改计算公式A[i] + A[j] + i - j,对于一个节点j,其A[j] - j时不变的,就把公式变成了A[i]+i A[j]-j,这样就将时间复杂度降低到了O(n)

题外话

感觉今天题解有点短,哈哈,那就扯点其他的话题,最近在拆分AQS的源码,其中用到了LockSupport这个类,之前我们要是阻塞或者释放线程,我们会使用wait()notifyAll()方法,但是这个方法来自Object中,在调用这两个方法前必须先获得锁对象,这限制了其使用场合:只能在同步代码块中。

  synchronized (obj) {
try {
obj.wait();//阻塞当前
} catch (InterruptedException e) {
 e.printStackTrace();
}
}
 synchronized (obj) {
 obj.notifyAll();
}

其实,我们还可以使用其他方法,就是LockSupport类,这个类不会抛出InterruptedException 异常

Thread show = new Thread(() -> {
LockSupport.park();
}, "a");
show.start();
LockSupport.unpark(show);

LockSupport是对线程进行的操作,使用LockSupport.unpark(Thread thread)唤醒线程,因为需要线程作参数,而AQS正好是对线程的操作,使用LockSupport恰到好处。