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

题目描述

给定正整数数组 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恰到好处。

清水1024