1005.K次取反后最大化的数组和

思路：

1. 优先取反 绝对值最大的负数
2. 如果没有负数，不断取反 绝对值最小的数，直到次数 K 耗尽

取反最小数有一个优化技巧：

1. 如果 K 为偶数，则取反 K 次后，正负不变。
2. 如果 K 为奇数，则取反 K 次后，正负变化。

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        # 按照绝对值从大到小排序，确保优先反转绝对值最大的负数
        nums.sort(key=lambda x: -abs(x))
        for i in range(len(nums)):
            if nums[i] < 0 and k > 0:
                nums[i] *= -1
                k -= 1
        # 取反 绝对值最小值
        if k % 2 != 0:
            nums[-1] *= -1
        
        return sum(nums)

134.加油站

思路：我们可以计算 每个加油站的剩余量 rest[i] = gas[i] - cost[i]。从 i = 0，开始累加每个加油站的 rest[i]，得到 curSum，如果 curSum < 0，则说明 [0, i] 中的所有加油站都不能作为起始点。 

 

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:

        curSum = 0
        totalSum = 0
        start = 0

        for i in range(len(gas)):
            curSum += gas[i] - cost[i]
            totalSum += gas[i] - cost[i]

            if curSum < 0:
                start = i + 1
                curSum = 0

        if totalSum < 0:
            return -1
        
        return start

135.分发糖果

• 先确定右边评分大于左边的情况（也就是从前向后遍历）
• 再确定左孩子大于右孩子的情况（从后向前遍历）

class Solution:
    def candy(self, ratings: List[int]) -> int:

        n = len(ratings)

        candys = [1] * n

        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                candys[i] = candys[i - 1] + 1

        for i in range(n -2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                candys[i] = max(candys[i], candys[i + 1] + 1)
        return sum(candys)