简述
贪心算法是指，在每次作出决策时，只考虑采取当前意义下的最优策略。因此，运用贪心算法时要求整体的最优可以由局部的最优导出。
例题目录
（目前简书不支持跳转，各位看官自行下滑吧）
例题
1、买卖股票的最佳时机 II
题目描述：
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
算法
只需要考虑每相邻两天的股价，如果当前的股价比前一天的股价
高，那
就可以加到总利润里面。
可能有人会问同一天不能同时进行买和卖，如果，按照这种算法，第二天会同时进行买和卖，即会发生：
和
，这不符合题意啊。
不要慌，虽然在算法中第二天会同时进行买和卖，其实这两次交易的总利润等价于只进行一次交易的利润，即。因为这是在一段上坡，波峰减去波谷的差值等于把上坡分成多段的差值之和。
代码
class Solution:
def maxProfit(self, prices: List[int]) -> int:
profit = 0
for i in range(len(prices) - 1):
if prices[i+1] > prices[i]:
profit += (prices[i+1] - prices[i])
return profit
时间复杂度：O(n)
2、无重叠区间
题目描述：
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意:
可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
示例 1:
输入: [ [1,2], [2,3], [3,4], [1,3] ]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
算法
从起点的贪心算法：
- 对集合按起点进行排序；
- 记录前一个区间的终点pos，对于当前区间i，
如果intervals[i].start >= pos，则：count+=1，pos=intervals[i].end;
如果intervals[i].start < pos，再分为：
如果intervals[i].end < pos，则：pos=intervals[i].end
从终点的贪心算法： - 对集合按终点进行排序；
- 记录前一个区间的终点pos，对于当前区间i，
如果intervals[i].start >= pos，则：count+=1，pos=intervals[i].end；
对于从终点的贪心算法，只需要判断intervals[i].start >= pos的情况，因为已经按终点从小到大排好序了，当前的终点一定大于等于pos，所以就少了从起点贪心的第二个“如果”。
因为题目问的是需要移除的最小区间数，以上算法的count是最大保留的区间数，因此用区间集合长度减去count就是所求。
代码
# 从起点贪心
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
n = len(intervals)
if n == 0:
return 0
intervals.sort(key=lambda x: x[0])
count = 1
pos = intervals[0][1]
for i in range(1, n):
if intervals[i][0] >= pos:
pos = intervals[i][1]
count += 1
else:
if intervals[i][1] < pos:
pos = intervals[i][1]
return n - count
# 从终点贪心
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
n = len(intervals)
if n == 0:
return 0
intervals.sort(key=lambda x: x[1])
res = 1
end = intervals[0][1]
for i in range(1, n):
if intervals[i][0] >= end:
end = intervals[i][1]
res += 1
return n - res
时间复杂度：
排序+遍历集合：O(nlogn) + O(n) ≈ O(nlogn)
相似题目
3、防晒
题目描述
有C头奶牛进行日光浴，第i头奶牛需要minSPF[i]到maxSPF[i]单位强度之间的阳光。
每头奶牛在日光浴前必须涂防晒霜，防晒霜有L种，涂上第i种之后，身体接收到的阳光强度就会稳定为SPF[i]，第i种防晒霜有cover[i]瓶。
求最多可以满足多少头奶牛进行日光浴。
算法
- 先按minSPF从大到小对奶牛进行排序；
- 按SPF从大到小对防晒霜进行排序；
- 遍历奶牛，选择可用的SPF值最大的。
为什么要选择SPF最大的呢？
假设当前奶牛可选的防晒霜是x和y，并且SPF[x] < SPF[y]，则后面的奶牛只可能出现：“x，y都能用”，“x，y都不能用”，“x能用，y不能用”这三种情况之一。如果我们选择了y，则对整体的影响比选择较小的x更好。
代码
# 读入数据
C, L = map(int, input().split())
min_max_SPF = [[0] * 2 for _ in range(C)]
for i in range(C):
m1, m2 = map(int, input().split())
min_max_SPF[i][0], min_max_SPF[i][1]= m1, m2
SPF_cover = [[0] * 2 for _ in range(L)]
for i in range(L):
s, c = map(int, input().split())
SPF_cover[i][0], SPF_cover[i][1] = s, c
# 按min从从大到小排序
min_max_SPF.sort(key=lambda x: x[0], reverse=True)
SPF_cover.sort(key=lambda x: x[0], reverse=True)
ans = 0
# 遍历
for m1, m2 in min_max_SPF:
for i, tup in enumerate(SPF_cover):
SPF, cover = tup
if m1 <= SPF <= m2 and cover > 0:
SPF_cover[i][1] -= 1
ans += 1
break
print(ans)
时间复杂度：O(n^2)
说明：这道题目来自AcWing，数据输入和输出的方式和leetcode不太一样。
4、畜栏预定
题目描述
有N头牛在畜栏中吃草。
每个畜栏在同一时间段只能提供给一头牛吃草，所以可能会需要多个畜栏。
给定N头牛和每头牛开始吃草的时间A以及结束吃草的时间B，每头牛在[A,B]这一时间段内都会一直吃草。
当两头牛的吃草区间存在交集时（包括端点），这两头牛不能被安排在同一个畜栏吃草。
求需要的最小畜栏数目和每头牛对应的畜栏方案。
算法
- 按开始时间对牛进行排序；
- 维护一个数组s，记录当前畜栏最后牛离场的时间；
- 遍历每头牛，在s中寻找一个当前牛的开始时间大于畜栏结束时间的合适畜栏。若找到了，则把找到的畜栏的结束时间改成当前牛的；若没有找到，则在s中添加一个畜栏，记录当前牛的结束时间。
代码
# 读取数据
n = int(input())
cows = [[0] * 3 for _ in range(n)]
for i in range(n):
cows[i][0], cows[i][1], cows[i][2]= *map(int, input().split()), i
# 按开始时间从小到大排序
cows.sort(key=lambda x: x[0])
s = []
res = [0] * n
for tup in cows:
start, end, i = tup
if not s: # 开始时s为空
s.append(end)
res[i] = 0
else:
# 遍历s，寻找一个合适的畜栏
for j, t in enumerate(s):
if start > t:
s[j] = end
res[i] = j
break
else: # 在已有的畜栏中没有合适的
s.append(end)
res[i] = len(s) - 1
# 打印结果
print(len(s))
for r in res:
print(r+1)
时间复杂度：O(n^2)
5、雷达设备
题目描述
假设海岸是一条无限长的直线，陆地位于海岸的一侧，海洋位于另外一侧。
每个小岛都位于海洋一侧的某个点上。
雷达装置均位于海岸线上，且雷达的监测范围为d，当小岛与某雷达的距离不超过d时，该小岛可以被雷达覆盖。
我们使用笛卡尔坐标系，定义海岸线为x轴，海的一侧在x轴上方，陆地一侧在x轴下方。
现在给出每个小岛的具体坐标以及雷达的检测范围，请你求出能够使所有小岛都被雷达覆盖所需的最小雷达数目。
算法
- 计算每个岛在x轴上的雷达可选范围[l[i], r[i]]；
- 用一个变量pos维护最后一台雷达的监控位置；
- 遍历每个岛在x轴上的映射，若l[i] > pos，则count+=1，pos=r[i]；否则，pos=min(pos, l[i])
代码
import math
# 获取输入
n, d = map(int, input().split())
islands = [[0] * 2 for _ in range(n)]
for i in range(n):
islands[i][0], islands[i][1] = map(int, input().split())
def main():
# 将island的(x, y)转化为x轴上的(l, r)
for i in range(n):
x, y = islands[i]
tmp = d ** 2 - y ** 2
if tmp < 0:
return -1
l, r = x - math.sqrt(tmp), x + math.sqrt(tmp)
islands[i] = [l, r]
# 按l从小到大排序
islands.sort(key=lambda x: x[0])
pos = float('-inf')
ans = 0
for l, r in islands:
if l > pos:
ans += 1
pos = r
else:
pos = min(pos, r)
return ans
print(main())
时间复杂度：O(n)
相似题目
6、国王游戏
题目描述
恰逢 H 国国庆,国王邀请 n 位大臣来玩一个有奖游戏。
首先,他让每个大臣在左、右手上面分别写下一个整数,国王自己也在左、右手上各写一个整数。
然后,让这 n 位大臣排成一排,国王站在队伍的最前面。
排好队后,所有的大臣都会获得国王奖赏的若干金币,每位大臣获得的金币数分别是:
排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数,然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏,所以他想请你帮他重新安排一下队伍的顺序,使得获得奖赏最多的大臣,所获奖赏尽可能的少。
注意,国王的位置始终在队伍的最前面。
算法
按左右手乘积从小到大的顺序排练即为最优排列方案。
代码
# 获取输入
n = int(input())
l_k, r_k = map(int, input().split())
array = [[0] * 3 for _ in range(n)]
for i in range(n):
l, r = map(int, input().split())
array[i] = [l, r, l * r]
array.sort(key=lambda x: x[2])
ans = 0
tmp = l_k
for l, r, _ in array:
total = tmp // r
ans = max(ans, total)
tmp *= l
print(ans)
时间复杂度：O(nlogn)
7、跳跃
题目描述
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]
输出: 2
说明:
假设你总是可以到达数组的最后一个位置。
算法
从前往后遍历nums，用pos和next_pos分别记录当前步能到达的最大位置和下一步能到达的最大位置。
由于题目保证能达到最后一个位置，因此只用遍历到倒数第二个位置。
代码
class Solution:
def jump(self, nums: List[int]) -> int:
step, next_pos, pos = 0, 0, 0
for i in range(len(nums) - 1):
next_pos = max(max_pos, nums[i] + i)
if pos == i:
step += 1
pos = max_pos
return step
时间复杂度：O(n)
题目变化 (LeetCode 55.跳跃游戏)：
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:
输入: [2,3,1,1,4]
输出: true
算法：
从前往后遍历 nums，pos 用于记录能到达的最大位置，
当 i <= pos 时，更新pos到能到达的最大位置；
当 i > pos 时，直接返回 False。
代码：
class Solution:
def canJump(self, nums: List[int]) -> bool:
n, pos = len(nums), 0
for i in range(n):
if i <= pos:
pos = max(pos, i + nums[i])
if pos >= n - 1:
return True
else:
return False
return False
时间复杂度：O(n)
8、 单调递增的数字
题目描述
给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）
示例 1:
输入: N = 10
输出: 9
示例 2:
输入: N = 332
输出: 299
算法
寻找原数中非递增的数的前一位，若前一位之前有相等的数，则再往相等数的第一位，将这位数减 1，这位数后面的位数全部置为 9。由于是从前往后递增，所以这一位不会是 0。
代码
class Solution:
def monotoneIncreasingDigits(self, N: int) -> int:
"""
寻找原数组中不满足递增的数的前一位
"""
arr = list(map(int, list(str(N))))
index = -1
for i in range(len(arr) - 1):
if arr[i] > arr[i+1]: # 非递增
while i > 0: # 找到相等数的第一个
if arr[i] == arr[i-1]:
index = i - 1
i -= 1
else:
break
if index == -1:
index = i
break
if index != -1:
arr[index] -= 1
for i in range(index+1, len(arr)):
arr[i] = 9
return int(''.join(map(str, arr)))
时间复杂度：O(n)
