欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

一天一大 leet(最佳观光组合)难度:中等 DAY-17

程序员文章站 2022-05-07 23:02:02
...

20200617

一天一大 leet(最佳观光组合)难度:中等 DAY-17

题目(难度:困难):

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

提示

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

抛砖引玉

一天一大 leet(最佳观光组合)难度:中等 DAY-17

A[i] + A[j] + i - j (i < j)

拆分公式

  • (A[i] + i) + (A[j] - j)
  • 循环前面一个数组加自身索引,后面一个数字减自身索引
  • A[i] + i 取数组中最大值,这样分别与 A[j] - j 相加才能取到最大值
    • 如果当前的 A[i] + i 小于上一个和则指针不切换,依次向后查询 A[j] - j
    • 如果当前的 A[i] + i 大于上一个和则指针切换成较大值
/**
 * @param {number[]} A
 * @return {number}
 */
var maxScoreSightseeingPair = function (A) {
  let _result = 0,
    middleValue = A[0] + 0
  for (let i = 1; i < A.length; i++) {
    _result = Math.max(A[i] + middleValue - i, _result)
    middleValue = Math.max(middleValue, A[i] + i)
  }
  return _result
}

官方答案

/**
 * @param {number[]} A
 * @return {number}
 */
var maxScoreSightseeingPair = function (A) {
  var ans = 0, mx = A[0] + 0;
  for (int j = 1; j < A.length; ++j) {
      ans = max(ans, mx + A[j] - j);
      // 边遍历边维护
      mx = max(mx, A[j] + j);
  }
  return ans;
}

其他解法

/**
 * @param {number[]} A
 * @return {number}
 */
var maxScoreSightseeingPair = function (A) {
  let res = 0,
    prev = 0
  for (let i = 1; i < A.length; i++) {
    prev = Math.max(prev, A[i - 1] + i - 1) //prev是前i-1个元素中A[m]+m的最大值
    res = Math.max(res, prev + A[i] - i)
  }
  return res
}

菜鸟的自白

  • 几种思路基本是一致的
  • 需要注意的地方: i<ji < j所有指针只能从 i 开始,另外如果忽略了这个限制条件使用 A[j]+j 那结果都会普遍变大

博客: 小书童博客(http://gaowenju.com)

公号: 坑人的小书童
一天一大 leet(最佳观光组合)难度:中等 DAY-17