跳转至

3730. Maximum Calories Burnt from Jumps 🔒

题目描述

You are given an integer array heights of size n, where heights[i] represents the height of the ith block in an exercise routine.

You start on the ground (height 0) and must jump onto each block exactly once in any order.

  • The calories burned for a jump from a block of height a to a block of height b is (a - b)2.
  • The calories burned for the first jump from the ground to the chosen first block heights[i] is (0 - heights[i])2.

Return the maximum total calories you can burn by selecting an optimal jumping sequence.

Note: Once you jump onto the first block, you cannot return to the ground.

 

Example 1:

Input: heights = [1,7,9]

Output: 181

Explanation:​​​​​​​

The optimal sequence is [9, 1, 7].

  • Initial jump from the ground to heights[2] = 9: (0 - 9)2 = 81.
  • Next jump to heights[0] = 1: (9 - 1)2 = 64.
  • Final jump to heights[1] = 7: (1 - 7)2 = 36.

Total calories burned = 81 + 64 + 36 = 181.

Example 2:

Input: heights = [5,2,4]

Output: 38

Explanation:

The optimal sequence is [5, 2, 4].

  • Initial jump from the ground to heights[0] = 5: (0 - 5)2 = 25.
  • Next jump to heights[1] = 2: (5 - 2)2 = 9.
  • Final jump to heights[2] = 4: (2 - 4)2 = 4.

Total calories burned = 25 + 9 + 4 = 38.

Example 3:

Input: heights = [3,3]

Output: 9

Explanation:

The optimal sequence is [3, 3].

  • Initial jump from the ground to heights[0] = 3: (0 - 3)2 = 9.
  • Next jump to heights[1] = 3: (3 - 3)2 = 0.

Total calories burned = 9 + 0 = 9.

 

Constraints:

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

解法

方法一：贪心 + 排序

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

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

具体步骤如下：

  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;
}

评论