贪心算法
常见题解
55. 跳跃游戏
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
提示：
1 <= nums.length <= 3 * 104
0 <= nums[i] <= 105
题解
对于这道题，只要求我们返回是否可以跳到最后节点，并没有让我们用最优解，所以我们可以用贪心算法求局部最优，用maxJump存储当前可以跳跃的最大距离，然后遍历数组，如果i小于等于maxJump，则更新最大的跳跃距离，最后如果maxJump大于n-1，则说明可以达到。
代码
class Solution:
def canJump(self, nums: List[int]) -> bool:
n = len(nums)
# 可以跳跃的最大距离
maxJump = 0
for i in range(n):
#
if i <= maxJump:
maxJump = max(maxJump, i + nums[i])
if maxJump >= n - 1:
return True
return False
135. 分发糖果
老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
你需要按照以下要求，帮助老师给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？
示例 1：
输入：[1,0,2]
输出：5
解释：你可以分别给这三个孩子分发 2、1、2 颗糖果。
示例 2：
输入：[1,2,2]
输出：4
解释：你可以分别给这三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这已满足上述两个条件。
阶梯思路
解题思路：
- 先分给每个孩子1个糖果
- 从左至右遍历，如果右孩子分数大于左孩子，那么右孩子的糖果等于左孩子的糖果+1
- 从右至左遍历，如果左孩子分数大于右孩子，并且右孩子的糖果数量大于等于左孩子的，则左孩子的糖果数量等于右孩子的+1
class Solution:
def candy(self, ratings: List[int]) -> int:
candies = [1] * len(ratings)
for i in range(1, len(ratings)):
if ratings[i] > ratings[i - 1]:
candies[i] = candies[i - 1] + 1
for i in range(len(ratings) - 2, -1, -1):
if ratings[i] > ratings[i + 1] and candies[
i + 1] >= candies[i]:
candies[i] = candies[i + 1] + 1
return sum(candies)