贪心算法是一种基于贪心思想的算法，它每次选择当前最优的解决方案，从而得到全局最优解。具体来说，贪心算法在每一步都做出局部最优选择，希望通过这种方式最终达到全局最优解。贪心算法通常适用于问题具有最优子结构性质和无后效性的情况。尽管贪心算法并不总是能够得到最优解，但它通常具有高效、简单等优点，并且在许多实际问题中得到了广泛应用。
一般来说，可以从以下几个方面考虑如何区别题目要使用贪心算法还是动态规划算法：
1、问题的性质：贪心算法适用于具有最优子结构性质和无后效性的问题，而动态规划算法则适用于具有重叠子问题和最优子结构性质的问题。
2、对时间复杂度的要求：贪心算法通常比动态规划算法更加高效，但并不总能得到最优解。如果对时间复杂度有较高的要求，可以首先考虑贪心算法；否则可以使用动态规划算法。
3、解决问题的方式：贪心算法通常是从局部最优解推导出全局最优解，即每次都选择当前最优解，并期望通过这种方式得到最终的最优解。而动态规划算法则是通过将问题分解成多个子问题，并保存已经求解过的子问题的结果，然后再利用这些子问题的结果求解更大的子问题，最终得到全局最优解。
4、是否存在贪心选择性质或者无后效性质：关键在于是否能够证明问题具有贪心选择性质或者无后效性质，如果问题确实具有这些性质，那么使用贪心算法也许是一个较好的选择。
https://leetcode.cn/problems/assign-cookies/description/
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g.sort()
s.sort()
i, j = 0, 0
while i < len(g) and j < len(s):
if g[i] <= s[j]:
i += 1
j += 1
return i
https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/
给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
以这种方式修改数组后，返回数组 可能的最大和 。
class Solution:
def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
nums.sort()
for i in range(len(nums)):
if nums[i] < 0 and k > 0:
nums[i] = -nums[i]
k -= 1
else:
break
nums.sort()
if k % 2 == 1:
nums[0] = -nums[0]
return sum(nums)
https://leetcode.cn/problems/lemonade-change/
使用贪心算法解决该问题，具体步骤如下：
1、初始化变量 fives, tens 为 0，分别表示手中拥有的 5 元和 10 元数量。
2、对于每个顾客支付的钞票金额 bill，进行如下操作：
3、如果成功为所有顾客找到了零钱，则返回 True。
class Solution:
def lemonadeChange(self, bills: List[int]) -> bool:
fives = tens = 0
for bill in bills:
if bill == 5:
fives += 1
elif bill == 10:
if not fives:
return False
fives -= 1
tens += 1
else:
if tens and fives:
tens -= 1
fives -= 1
elif fives >= 3:
fives -= 3
else:
return False
return True
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
if len(nums) < 2:
return len(nums)
up = down = 1
for i in range(1, len(nums)):
if nums[i] > nums[i-1]:
up = down + 1
elif nums[i] < nums[i-1]:
down = up + 1
return max(up, down)
https://leetcode.cn/problems/monotone-increasing-digits/
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
class Solution:
def monotoneIncreasingDigits(self, n: int) -> int:
s = str(n)
i = 1
while i < len(s) and s[i - 1] <= s[i]:
i += 1
if i < len(s):
while i > 0 and s[i - 1] > s[i]:
s = s[:i - 1] + str(int(s[i - 1]) - 1) + '9' * (len(s) - i)
i -= 1
return int(s)
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
在贪心策略中，前一天价格低就买入，然后在今天卖出。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
profit = 0
for i in range(1,len(prices)):
if prices[i] > prices[i-1]:
profit+=(prices[i]-prices[i-1])
return profit
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/
给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
if not prices:
return 0
profit = 0
buy_price = prices[0]
for i in range(1, len(prices)):
# 如果当前价格比之前买入价加手续费高，就可以卖出股票并获得利润
if prices[i] >= buy_price + fee:
profit += prices[i] - (buy_price + fee)
buy_price = prices[i] - fee # 更新买入价为当前价减去手续费
# 如果当前价格比之前买入价便宜，就考虑更新买入价
elif prices[i] < buy_price:
buy_price = prices[i]
return profit
https://leetcode.cn/problems/candy/description/
class Solution(object):
def candy(self, ratings):
"""
:type ratings: List[int]
:rtype: int 贪心策略，两遍遍历。第一遍右边元素比左遍元素大，则糖果为左边糖果加1.第2遍左边元素比右边元素大，则糖果为右边加1或者或者为本身糖果数量。
"""
if len(ratings)<2:
return len(ratings)
assign=[1 for _ in ratings]
for i in range(1,len(ratings),1):
if ratings[i]>ratings[i-1]:
assign[i]=assign[i-1]+1
for i in range(len(ratings)-1,0,-1):
if ratings[i-1]>ratings[i]:
assign[i-1]=max(assign[i-1],assign[i]+1)
return sum(assign)
https://leetcode.cn/problems/queue-reconstruction-by-height/description/
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。
class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
# 按照身高从高到低排列，如果身高相同则按照前面大于等于身高的人数从小到大排序
people.sort(key=lambda x: (-x[0], x[1]))
queue = []
# 将每个人插入到队列中，位置由前面大于等于身高的人数决定
for p in people:
queue.insert(p[1], p)
return queue
https://leetcode.cn/problems/jump-game/description/
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
class Solution:
def canJump(self, nums: List[int]) -> bool:
n = len(nums)
farthest = 0
for i in range(n):
if i <= farthest:
farthest = max(farthest, i + nums[i])
if farthest >= n - 1:
return True
return False
https://leetcode.cn/problems/jump-game-ii/description/
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
class Solution:
def jump(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return 0
max_pos, step, end = 0, 0, 0
for i in range(n-1):
max_pos = max(max_pos, i + nums[i])
if i == end:
end = max_pos
step += 1
return step
https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
if not points:
return 0
# 按照气球结束坐标从小到大排序
points.sort(key=lambda x:x[1])
# 初始化箭的射出位置为第一个气球的结束坐标
arrow_pos = points[0][1]
count = 1
for i in range(1, len(points)):
# 如果下一个气球的开始坐标大于当前箭的射出位置，则需要再发射一支箭
if points[i][0] > arrow_pos:
arrow_pos = points[i][1]
count += 1
return count
https://leetcode.cn/problems/non-overlapping-intervals/submissions/417134877/
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
具体实现过程如下：
首先判断输入是否为空，如果为空则直接返回0。
对输入列表按照每个区间的结束位置进行排序，即按照x[1]排序。
初始化变量end为第一个区间的结束位置，count为1，表示当前至少需要保留一个区间。
遍历排序后的区间列表，若当前区间的开始位置大于等于end，则说明该区间与前一个区间不重叠，将end更新为当前区间的结束位置，同时count加1。
若当前区间的开始位置小于end，则说明该区间与前一个区间重叠，则需要移除其中一个区间。因为已经将区间按照结束位置排序，所以优先保留结束位置更早的区间，因此将end更新为前一个区间的结束位置和当前区间的结束位置中较小的那个。
最终返回需要移除的区间数量，即总区间数减去保留的区间数。
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
if not intervals:
return 0
intervals.sort(key=lambda x: x[1])
end = intervals[0][1]
count = 1
for i in range(1, len(intervals)):
if intervals[i][0] >= end:
end = intervals[i][1]
count += 1
else:
end = min(end, intervals[i][1])
return len(intervals) - count
https://leetcode.cn/problems/partition-labels/description/
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
遍历字符串，对于每个字符记录它最后一次出现的位置；
维护一个起始位置和结束位置，表示当前片段的范围；
如果当前位置等于结束位置，说明当前位置是一个片段的结束位置，将该片段长度添加到结果数组中，并将起始位置设为结束位置的下一个位置；
最终返回结果数组。
class Solution:
def partitionLabels(self, s: str) -> List[int]:
last = {c:i for i, c in enumerate(s)}
start = end = 0
res = []
for i, c in enumerate(s):
end = max(end, last[c])
if i == end:
res.append(end - start + 1)
start = end + 1
return res