LeetCode-Solutions/C++/maximum-calories-burnt-from-jumps.cpp at master · kamyu104/LeetCode-Solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// Time:  O(nlogn)
// Space: O(1)

// sort, greedy
class Solution {
public:
    long long maxCaloriesBurnt(vector<int>& heights) {
        ranges::sort(heights);
        int left = 0, right = size(heights) - 1;
        int64_t result = static_cast<int64_t>(0 - heights[right]) * (0 - heights[right]);
        while (left != right) {
            result += static_cast<int64_t>(heights[right] - heights[left]) * (heights[right] - heights[left]);
            --right;
            if (left == right) {
                break;
            }
            result += static_cast<int64_t>(heights[left] - heights[right]) * (heights[left] - heights[right]);
            ++left;
        }
        return result;
    }
};

// Time:  O(nlogn)
// Space: O(1)
// sort, greedy
class Solution2 {
public:
    long long maxCaloriesBurnt(vector<int>& heights) {
        ranges::sort(heights);
        int left = 0, right = size(heights) - 1;
        int64_t result = static_cast<int64_t>(0 - heights[right]) * (0 - heights[right]);
        for (int8_t d = 0; left != right;) {
            result += static_cast<int64_t>(heights[right] - heights[left]) * (heights[right] - heights[left]);
            left += d;
            d ^= 1;
            right -= d;
        }
        return result;
    }
};