每日题解: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恰到好处。

最近的文章

每日题解:LeetCode 1028. 从先序遍历还原二叉树

题目地址题目描述我们从二叉树的根节点 root 开始进行深度优先搜索。在遍历中的每个节点处,我们输出 D 条短划线(其中 D 是该节点的深度),然后输出该节点的值。(如果节点的深度为 D,则其直接子节点的深度为 D + 1。根节点的深度为 0)。如果节点只有一个子节点,那么保证该子节点为左子节点。给…

继续阅读
更早的文章

每日题解:LeetCode 297. 二叉树的序列化与反序列化

题目地址题目描述序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑,你只需要保证一个二…

继续阅读