【LeetCode 1014】最佳观光对 Best Sightseeing Pair

末蓝、 2021-09-22 23:32 132阅读 0赞

LeetCode 1014题，属于数组类型的题目，题意：  
![在这里插入图片描述][20190405123108407.png]  
翻译成中文，就是要找数组中的两个点，满足：

*  `A[i] + A[j] + i - j`的值最大
 *  且 `i < j`

![在这里插入图片描述][20190405123120336.png]  
![在这里插入图片描述][20190405123133907.png]  
思路：  
最快速的想法，就是直接暴力求解：  
因为实际上就是求符合题意的两个点能获得的最大值，直接两个循环：

public int maxScoreSightseeingPair(int[] A) { 
            if (A == null || A.length == 0) return 0;
            int max = 0;
            for (int i = 0; i < A.length; i++) { 
                for (int j = i + 1; j < A.length; j++) { 
                    if (A[i] + A[j] + i - j > max) { 
                        max = A[i] + A[j] + i - j;
                    }
                }
            }
            return max;
        }

但直接暴力解复杂度 O(n²)，LeetCode直接超时了，所以我们要变换思路：  
我们观察：`A[i] + A[j] + i - j`，可以拆分为：`A[i] + i`跟`A[j] - j`，所以，题目相当于，找出一个点 i，且在改点之后，有一个点 j，使得`A[i] + i`跟`A[j] - j`的和获得最大值。  
我们可以想到，先遍历一遍数组，记录在当前 i可以获得的`A[i] + i`的最大值`temp[]`，再第二次遍历数组，看在哪个点，可以获得`temp[i[ + A[i] - i`的最大值，代码：

public int maxScoreSightseeingPair(int[] A) { 
            if (A == null || A.length == 0) return 0;
            // 用于记录每个点之前，能获取的 A[i] + i的最大值
            int[] temp = new int[A.length];
            int max = Integer.MIN_VALUE;
            // 第一次遍历，用于更新 temp[]
            for (int i = 0; i < A.length - 1; i++) { 
                if (A[i] + i > temp[i]) { 
                    // 若当前 i点的组合大于原始组合，则更新
                    temp[i + 1] = A[i] + i;
                } else { 
                	// 当前 i点组合未能获得更大的组合值
                    temp[i + 1] = temp[i];
                }
            }
            // 第二次遍历
            for (int i = 0; i < A.length; i++) { 
                if (temp[i] + A[i] - i > max) { 
                    max = temp[i] + A[i] - i;
                }
            }
            return max;
        }

该解法的时间复杂度为 O(n)，空间复杂度为 O(n)。但该解法遍历了两次数组，而且还有空间开销，那我们可不可以只遍历一次且常数级别的空间开销呢？  
其实我们发现：上面的 `temp[]`用于记录在这个点之前能获取的 `A[i] + i`组合的最大值，其实我们可以用一个变量进行记录即可，因此，修改代码，有：

public int maxScoreSightseeingPair(int[] A) { 
            if (A == null || A.length == 0) return 0;
            int i = 0, max = Integer.MIN_VALUE;
            for (int j = 1; j < A.length; j++) { 
                if (A[i] + A[j] + i - j > max) { 
                    max = A[i] + A[j] + i - j;
                }
                // 更新 A[i] + i组合能获得最大值的下标
                if (i + A[i] < j + A[j]) { 
                    i = j;
                }
            }
            return max;
        }

时间复杂度 O(n)，空间复杂度 O(1)  
提交结果：  
![在这里插入图片描述][20190405124828175.png]

[其他 LeetCode 题目解析][LeetCode]

[20190405123108407.png]: /images/20210920/368581512f3246d895ea6b246bbd85f5.png
[20190405123120336.png]: /images/20210920/3b23ca6e206241189dfbe8752cd2e725.png
[20190405123133907.png]: /images/20210920/a0398913a9ca470a858afd9607fc71d0.png
[20190405124828175.png]: /images/20210920/c032644682744b249a0e75354cf1fd7f.png
[LeetCode]: https://blog.csdn.net/applying/category_9629399.html