跳转至

3730. 跳跃燃烧的最大卡路里 🔒

题目描述

给定一个长度为 n 的整数数组 heights，其中 heights[i] 表示训练计划中第 i 个块的高度。

你从地面（高度0）开始，必须 按照任意顺序跳到每个方块上，且只能跳 一次。

  • 从一个高度为 a 的块起跳到另一个高度为 b 的块所消耗的卡路里是 (a - b)2。
  • 从地面跳到所选的第一个方块高度 heights[i] 所 消耗的卡路里 是 (0 - heights[i])2。

返回通过选择最优跳跃序列所能燃烧的 最大 总卡路里。

注意：一旦你跳到第一个方块上，就无法返回地面。

 

示例 1：

输入：heights = [1,7,9]

输出：181

解释：

最优序列是 [9, 1, 7]。

  • 从地面到 heights[2] = 9 的初始跳跃：(0 - 9)2 = 81。
  • 下一次跳跃到 heights[0] = 1：(9 - 1)2 = 64。
  • 最后一次跳跃到 heights[1] = 7：(1 - 7)2 = 36。

消耗的总卡路里 = 81 + 64 + 36 = 181。

示例 2：

输入：heights = [5,2,4]

输出：38

示例：

最优序列是 [5, 2, 4]。

  • 从地面到 heights[0] = 5 的初始跳跃：(0 - 5)2 = 25。
  • 下一次跳跃到 heights[1] = 2：(5 - 2)2 = 9。
  • 最后一次跳跃到 heights[2] = 4：(2 - 4)2 = 4。

消耗的总卡路里 = 25 + 9 + 4 = 38。

示例 3：

输入：heights = [3,3]

输出：9

示例：

最优序列是 [3, 3]。

  • 从地面到 heights[0] = 3 的初始跳跃：(0 - 3)2 = 9。
  • 下一次跳跃到 heights[1] = 3：(3 - 3)2 = 0。

消耗的总卡路里 = 9 + 0 = 9。

 

提示：

  • 1 <= n == heights.length <= 105
  • 1 <= heights[i] <= 105

解法

方法一：贪心 + 排序

思考

消耗是相邻高度差的平方，从 \(0\) 起跳且不能返回地面。差的平方对两端极值更敏感，排序后在最高与最低之间交替跳跃，可使每一步的落差尽量大。

根据题意，跳跃的顺序会影响总消耗的卡路里数。为了最大化卡路里消耗，我们可以采用贪心策略，优先跳跃高度差较大的块。

因此，我们可以先将块的高度进行排序，然后从最高的块开始跳跃，然后跳到最低的块，依此类推，直到所有块都被跳跃过。

具体步骤如下：

  1. 对数组 \(\text{heights}\) 进行排序。
  2. 初始化变量 \(\text{pre} = 0\)，表示上一个块的高度，变量 \(\text{ans} = 0\)，表示总消耗的卡路里数。
  3. 使用双指针，左指针 \(\text{l}\) 指向数组的开头，右指针 \(\text{r}\) 指向数组的结尾。
  4. 当 \(\text{l} < \text{r}\) 时，执行以下操作：
    1. 计算从上一个块跳到右指针指向的块的卡路里消耗，并将其加入 \(\text{ans}\)。
    2. 计算从右指针指向的块跳到左指针指向的块的卡路里消耗，并将其加入 \(\text{ans}\)。
    3. 更新 \(\text{pre}\) 为左指针指向的块的高度。
    4. 将左指针向右移动一位，右指针向左移动一位。
  5. 最后，计算从上一个块跳到中间块的卡路里消耗，并将其加入 \(\text{ans}\)。

时间复杂度 \(O(n \times \log n)\)，空间复杂度 \(O(\log n)\)。其中 \(n\) 是数组的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def maxCaloriesBurnt(self, heights: list[int]) -> int:
        heights.sort()
        pre = 0
        l, r = 0, len(heights) - 1
        ans = 0
        while l < r:
            ans += (heights[r] - pre) ** 2
            ans += (heights[l] - heights[r]) ** 2
            pre = heights[l]
            l, r = l + 1, r - 1
        ans += (heights[r] - pre) ** 2
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public long maxCaloriesBurnt(int[] heights) {
        Arrays.sort(heights);
        long ans = 0;
        int pre = 0;
        int r = heights.length - 1;
        for (int l = 0; l < r; ++l, --r) {
            ans += 1L * (heights[r] - pre) * (heights[r] - pre);
            ans += 1L * (heights[l] - heights[r]) * (heights[l] - heights[r]);
            pre = heights[l];
        }
        ans += 1L * (heights[r] - pre) * (heights[r] - pre);
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    long long maxCaloriesBurnt(vector<int>& heights) {
        ranges::sort(heights);
        long long ans = 0;
        int pre = 0;
        int r = heights.size() - 1;
        for (int l = 0; l < r; ++l, --r) {
            ans += 1LL * (heights[r] - pre) * (heights[r] - pre);
            ans += 1LL * (heights[l] - heights[r]) * (heights[l] - heights[r]);
            pre = heights[l];
        }
        ans += 1LL * (heights[r] - pre) * (heights[r] - pre);
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func maxCaloriesBurnt(heights []int) (ans int64) {
    sort.Ints(heights)
    pre := 0
    l, r := 0, len(heights)-1
    for l < r {
        ans += int64(heights[r]-pre) * int64(heights[r]-pre)
        ans += int64(heights[l]-heights[r]) * int64(heights[l]-heights[r])
        pre = heights[l]
        l++
        r--
    }
    ans += int64(heights[r]-pre) * int64(heights[r]-pre)
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function maxCaloriesBurnt(heights: number[]): number {
    heights.sort((a, b) => a - b);
    let ans = 0;
    let pre = 0;
    let [l, r] = [0, heights.length - 1];
    while (l < r) {
        ans += (heights[r] - pre) ** 2;
        ans += (heights[l] - heights[r]) ** 2;
        pre = heights[l];
        l++;
        r--;
    }
    ans += (heights[r] - pre) ** 2;
    return ans;
}

评论