LeetCode-Solutions/Python/maximum-calories-burnt-from-jumps.py 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
42
# Time:  O(nlogn)
# Space: O(1)

# sort, greedy
class Solution(object):
    def maxCaloriesBurnt(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        heights.sort()
        left, right = 0, len(heights)-1
        result = (0-heights[right])**2
        while left != right:
            result += (heights[right]-heights[left])**2
            right -= 1
            if left == right:
                break
            result += (heights[left]-heights[right])**2
            left += 1
        return result


# Time:  O(nlogn)
# Space: O(1)
# sort, greedy
class Solution2(object):
    def maxCaloriesBurnt(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        heights.sort()
        d = 0
        left, right = 0, len(heights)-1
        result = (0-heights[right])**2
        while left != right:
            result += (heights[right]-heights[left])**2
            left += d
            d ^= 1
            right -= d
        return result