今日任务

●  122.买卖股票的最佳时机II 

●  55. 跳跃游戏 

●  45.跳跃游戏II 

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

●  134. 加油站

●  135. 分发糖果  

122.买卖股票的最佳时机 II

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        ans = 0 
        for i in range(1, len(prices)):
            ans += max(0, prices[i]-prices[i-1])
        return ans

55. 跳跃游戏

本题贪心的关键是：不用拘泥于每次究竟跳几步，而是看覆盖范围，覆盖范围内一定是可以跳过来的，不用管是怎么跳的。

那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点！

def canJump(self, nums: List[int]) -> bool:
        largest = 0
        n = len(nums)
        for i in range(n-1):
            largest = max(largest, i+nums[i])
            if largest <= i:
                return False
        return largest >= n-1

45.跳跃游戏 II

本题解题关键在于：以最小的步数增加最大的覆盖范围，直到覆盖范围覆盖了终点。

//方法一 暴力法
//思考每一步能去的最大范围 使用min的方式进行
class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        ans = [10003  for _ in range(n)]
        ans[0] = 0
        for i in range(n):
            temp = ans[i] + 1
            for j in range(i+1, min(i+nums[i]+1, n)):
                ans[j] = min(ans[j], temp)
        return ans[-1]
            

//方法二 贪心算法
//想法是当前步数能覆盖的最大范围
//时间复杂度 O（N）
//空间复杂度 O（1）
class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        count = 0
        max_range = 0
        next_max_range = 0
        for i in range(n):
            next_max_range = max(next_max_range, i+nums[i])
            if max_range >= n-1:
                break
            if i == max_range:
                count += 1 
                max_range = next_max_range
            
        return count
            

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

别怕 可以sort两次

多练胆子才会大

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        n = len(nums)
        nums.sort()
        i = 0
        while i < n and nums[i] < 0 and k > 0:
            nums[i] = -nums[i]
            i += 1
            k -= 1
        if k > 0 :
            nums.sort()
            k = k%2
            if k == 1:
                nums[0] = -nums[0]
        ans = 0
        for j in nums:
            ans += j
        return ans

134. 加油站

首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。

从每一个点出发计算能连续到达的最大距离，因为已经确保了可以跑完

那我们就要求哪个点可以跑完

如果到达下一个点的油不够了 说明从出发点到现在这个点都不能作为出发点

因为正数+正数是大于正数的

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) < sum(cost):
            return -1
        
        total = res = 0
        
        for i in range(len(gas)):
            total += (gas[i] - cost[i])
            if total < 0:
                total = 0
                res = i + 1
        
        return res

135. 分发糖果

只考虑比旁边人大的情况，这样不用考虑变成负数，且满足最少1个的要求。

换位思考，比右边小和比左边大是一个意思

这是精髓

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

此时局部最优：只要右边评分比左边大，右边的孩子就多一个糖果，全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果

局部最优可以推出全局最优。

再确定左孩子大于右孩子的情况（从后向前遍历）

那么本题我采用了两次贪心的策略：

• 一次是从左到右遍历，只比较右边孩子评分比左边大的情况。
• 一次是从右到左遍历，只比较左边孩子评分比右边大的情况。

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        candy = [1 for _ in range(n)]
        for i in range(1, n):
            if ratings[i] > ratings[i-1]:
                candy[i] = candy[i-1]+1
        for i in range(n-2, -1, -1):
            if ratings[i] > ratings[i+1]:
                candy[i] = max(candy[i], candy[i+1]+1)
        return sum(candy)