etCode

通过做差可以得到利润序列然后只要利润需求的非负数求和就可以因为这里没有手续费某天买入之后买出可以等价为这几天连续买入卖出

class

这是一个常见的贪心算法问题。

我们从数组的第一个元素开始保持跟踪我们能到达的最远的下标。

然后我们迭代数组中的每个元素并更新我们能到达的最远下标。

如果我们能到达的最远下标大于或等于数组的长度我们就知道我们可以到达数组的最后一个元素。

以下是Python语言实现此算法的代码

def

记录了在迭代过程中可以跳到的最远的下标。

enumerate(nums)会遍历数组并且返回每个元素的索引i和值num。

如果当前索引i超过了我们可以跳到的最远的下标那么我们就返回False因为我们不能到达当前索引。

否则我们更新

max_jump

然后如果我们没有提前返回False那么在遍历完数组后我们就返回True因为我们可以到达数组的最后一个元素。

45.

的问题相似但是我们现在需要找出到达最后一个下标的最小跳跃次数。

我们可以追踪当前位置的最大跳跃范围并将其与最大跳跃范围内的所有位置的最大跳跃范围进行比较。

我们可以保留最大跳跃范围的索引然后当当前位置到达或超过当前的最大跳跃范围时我们更新最大跳跃范围并将跳跃次数加1。

def

记录了当前的最大跳跃范围。

如果当前索引i等于当前的最大跳跃范围那么我们更新

end

通过做差可以得到利润序列然后只要利润非负数求和即可没有手续费。

跳跃游戏:

同样是贪心算法找出到达最后一个下标的最小跳跃次数。

保持最大跳跃范围并逐步更新。