贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
例如，有一堆钞票，可以拿走十张，如果想达到最大的金额，要怎么拿？每次拿最大的，最终结果就是拿走最大数额的钱。每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。
再举一个例子，有一堆盒子，有一个背包体积为n，如何把背包尽可能装满，如果还每次选最大的盒子，就不行了。这时候就需要动态规划。动态规划的问题在下一个系列会详细讲解。
贪心算法并没有固定的套路，说白了就是常识性推导加上举反例。所以唯一的难点就是如何通过局部最优，推出整体最优。如果模拟可行，就可以试一试贪心策略，如果不可行，可能需要动态规划。
贪心算法一般分为如下四步：
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
其实这个分的有点细了，真正做题的时候很难分出这么详细的解题步骤，可能就是因为贪心的题目往往还和其他方面的知识混在一起。
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
输入: g = [1,2,3], s = [1,1] 输出: 1
解释: 你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。 虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。 所以你应该输出1。
求解思路：
局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。
可以尝试使用贪心策略，先将饼干数组和小孩数组排序。然后从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量。如图：
可以看出饼干9只有喂给胃口为7的小孩，才是整体最优解，并想不出反例，那么就可以撸代码了。
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
"""
思路2：优先考虑胃口
"""
g.sort() # 胃口排序
s.sort() # 饼干排序
child_num = len(g)
start_idx = len(s) - 1
satisfy_count = 0
for idx in range(child_num-1, -1, -1):
if start_idx >= 0 and g[idx] <= s[start_idx]:
start_idx -= 1
satisfy_count += 1
return satisfy_count如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
例如，[1, 7, 4, 9, 2, 5] 是一个 摆动序列，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组 nums，返回 nums 中作为 摆动序列 的 最长子序列的长度 。
示例 1：
输入：nums = [1,7,4,9,2,5] 输出：6 解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3)。
求解思路：
本题要求通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
如何修改？分析一下，要求删除元素使其达到最大摆动序列，应该删除什么元素？用示例二来举例，如图所示：
局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。
整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。
局部最优推出全局最优，并举不出反例，那么试试贪心！（为方便表述，以下说的峰值都是指局部峰值）
实际操作上，其实连删除的操作都不用做，因为题目要求的是最长摆动子序列的长度，所以只需要统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度）。这就是贪心所贪的地方，让峰值尽可能的保持峰值，然后删除单一坡度上的节点。
本题代码实现中，还有一些技巧，例如统计峰值的时候，数组最左面和最右面是最不好统计的。
例如序列[2,5]，它的峰值数量是2，如果靠统计差值来计算峰值个数就需要考虑数组最左面和最右面的特殊情况。所以可以针对序列[2,5]，可以假设为[2,2,5]，这样它就有坡度了即 preDiff = 0，如图：
针对以上情形，result初始为1（默认最右面有一个峰值），此时curDiff > 0 && preDiff <= 0，那么result++（计算了左面的峰值），最后得到的result就是2（峰值个数为2即摆动序列长度为2）。
另一种思路可以使用动态规划。
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
pre_elem = 0
cur_elem = 0
# 默认最后有一个山峰
count = 1
for i in range(len(nums) - 1):
cur_elem = nums[i+1] - nums[i]
if cur_elem * pre_elem <= 0 and cur_elem != 0:
count += 1
pre_elem = cur_elem
return count给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
求解思路一：暴力解法
暴力解法的思路，第一层for 就是设置起始位置，第二层for循环遍历数组寻找最大值
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int result = INT32_MIN;
int count = 0;
for (int i = 0; i < nums.size(); i++) { // 设置起始位置
count = 0;
for (int j = i; j < nums.size(); j++) { // 每次从起始位置i开始遍历寻找最大值
count += nums[j];
result = count > result ? count : result;
}
}
return result;
}
};以上暴力的解法C++勉强可以过，其他语言就不确定了。
求解思路二：贪心算法
贪心贪的是哪里？如果 -2 1 在一起，计算起点的时候，一定是从1开始，因为负数只会拉低总和，这就是贪心贪的地方！
-
局部最优：当前连续和为负数的时候立刻放弃，从下一个元素重新计算连续和，因为负数加上下一个元素 连续和只会越来越小。
-
全局最优：选取最大连续和。
局部最优的情况下，并记录最大的连续和，可以推出全局最优。
从代码角度上来讲：遍历nums，从头开始用count累积，如果count一旦加上nums[i]变为负数，那么就应该从nums[i+1]开始从0累积count了，因为已经变为负数的count，只会拖累总和。这相当于是暴力解法中的不断调整最大子序和区间的起始位置。
**区间终止位置不用调整么？ 如何才能得到最大连续和？**区间的终止位置，其实就是如果count取到最大值了，及时记录下来了。例如如下代码：
if (count > result) result = count;
这样相当于是用result记录最大子序和区间和（变相的算是调整了终止位置）。
如动画所示：
红色的起始位置就是贪心每次取count为正数的时候，开始一个区间的统计。
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
res = -float("inf")
sum_ptr = 0
for elem in nums:
sum_ptr += elem
if sum_ptr > res:
res = sum_ptr
if sum_ptr <= 0:
sum_ptr = 0
return res求解思路二：动态规划
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
"""
动态规划
--------
思路：比较 max（前面子序列和+当前第i个元素，当前第i个元素），存放到暂时变量中，
遍历nums列表，最后的结果即为最大子序列和
状态转移方程
"""
if len(nums) == 1:
return nums[0]
# 初始化子序列和
subseq = 0
# 初始化最大子序列和
res = nums[0]
# 遍历所有数字
for num in nums:
# 计算当前子序列和与当前数字的最大值
subseq = max(subseq + num, num)
res = max(subseq, res)
return reshttps://leetcode.cn/problems/best-time-to-buy-and-sell-stock/
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0。
求解思路一：贪心算法
一次遍历，需要维护两个指针，假设在第i天卖出股票，要获得最大利润，那么买入价格一定是前i-1天中的最低价格买入的，故可以用两个指针分别记录卖出的最低价格和当前的最高价格。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
max_profit = 0
# 卖出的最低价格
min_sell_price = float("inf")
for cur_price in prices:
max_profit = max(max_profit, cur_price-min_price)
min_sell_price = min(min_sell_price, cur_price)
return max_profit求解思路二：动态规划
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。返回你能获得的最大利润 。
求解思路一：贪心算法
这道题目可能我们只会想，选一个低的买入，在选个高的卖，在选一个低的买入.....循环反复。
如果想到其实最终利润是可以分解的，那么本题就很容易了！
如何分解呢？
假如第0天买入，第3天卖出，那么利润为：prices[3] - prices[0]。
相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。
此时就是把利润分解为每天为单位的维度，而不是从0天到第3天整体去考虑！
那么根据prices可以得到每天的利润序列：(prices[i] - prices[i - 1]).....(prices[1] - prices[0])。
如图：
第一天没有利润，至少要第二天才会有利润，所以利润的序列比股票序列少一天！
从图中可以发现，其实只需要收集每天的正利润即可，收集正利润的区间，就是股票买卖的区间，而我们只需要关注最终利润，不需要记录区间。那么只收集正利润就是贪心所贪的地方！
局部最优：收集每天的正利润，全局最优：求得最大利润。局部最优可以推出全局最优，找不出反例，试一试贪心！
class Solution:
def maxProfit(self, prices: List[int]) -> int:
max_profit = 0
for idx in range(1, len(prices)):
max_profit += max(prices[idx] - prices[idx-1], 0)
return max_profit求解思路二：动态规划
class Solution:
def maxProfit(self, prices: List[int]) -> int:
length = len(prices)
dp = [[0] * 2 for _ in range(length)]
dp[0][0] = -prices[0]
dp[0][1] = 0
for i in range(1, length):
dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]) #注意这里是和121. 买卖股票的最佳时机唯一不同的地方
dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])
return dp[-1][1]https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee
给定一个整数数组 prices，其中 prices[i] 表示第 i 天的股票价格；整数 fee 代表了交易股票的手续费用。你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要支付一次手续费。
求解思路：
在 122.买卖股票的最佳时机II 中使用贪心策略不用关心具体什么时候买卖，只要收集每天的正利润，最后就是最大利润。而本题有手续费，就要关心什么时候买卖，因为需要考虑买卖利润可能不足以手续费的情况。如果使用贪心策略，就是最低值买，最高值（如果算上手续费还盈利）就卖。
此时无非就是要找到两个点，买入日期，和卖出日期。
- 买入日期：其实很好想，遇到更低点就记录一下。
- 卖出日期：这个就不好算了，但也没有必要算出准确的卖出日期，只要当前价格大于（最低价格+手续费），就可以收获利润，至于准确的卖出日期，就是连续收获利润区间里的最后一天（并不需要计算是具体哪一天）。
所以我们在做收获利润操作的时候其实有三种情况：
- 情况一：收获利润的这一天并不是收获利润区间里的最后一天（不是真正的卖出，相当于持有股票），所以后面要继续收获利润。
- 情况二：前一天是收获利润区间里的最后一天（相当于真正的卖出了），今天要重新记录最小价格了。
- 情况三：不作操作，保持原有状态（买入，卖出，不买不卖）
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
# 最大盈利
max_profit = 0
# 选取很关键！！！记录最低价格
min_price = prices[0]
for i in range(1, len(prices)):
# case2
if prices[i] < min_price:
min_price = prices[i]
# case3
elif prices[i] >= min_price and prices[i] <= min_price + fee:
continue
# 计算利润
elif prices[i] > min_price + fee:
max_profit += prices[i] - min_price - fee
# case1
min_price = prices[i] - fee
return max_profit从代码中可以看出对情况一的操作，因为如果还在收获利润的区间里，表示并不是真正的卖出，而计算利润每次都要减去手续费，所以要让 min_price = prices[i] - fee，这样在明天收获利润的时候，才不会多减一次手续费！ 另外，情况三那块代码是可以删掉的，为了让代码表达清晰，所以没有精简。
给定一个非负整数数组 nums，你最初位于数组的 第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。
求解思路：
一开始看到题目可能会疑惑：如果当前位置元素如果是3，究竟是跳一步还是两步、三步呢？其实跳几步无所谓，关键在于可跳的覆盖范围。不一定非要明确一次究竟跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围。那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点。
每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。
贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。
如图：
i 每次移动只能在 cover 的范围内移动，每移动一个元素，cover得到该元素数值（新的覆盖范围）的补充，让 i 继续移动下去。而 cover 每次只取 max(该元素数值补充后的范围, cover本身范围)。如果 cover 大于等于了终点下标，直接 return true 就可以了。
class Solution:
def canJump(self, nums: List[int]) -> bool:
cover = 0
i = 0
if len(nums) == 1:
return True
while i <= cover:
cover = max(i + nums[i], cover)
if cover >= len(nums) - 1:
return True
i += 1
return False给你一个非负整数数组 nums，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。假设你总是可以到达数组的最后一个位置。
贪心求解思路：
- 局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。
- 整体最优：一步尽可能多走，从而达到最小步数。
本题需要统计两个覆盖范围：当前这一步的最大覆盖和下一步最大覆盖。不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最小步数。
如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。
如图：
class Solution:
def jump(self, nums: List[int]) -> int:
if len(nums) == 1:
return 0
ans = 0
cur_dist = 0
nxt_dist = 0
length = len(nums)
for i in range(length):
# i 表示当前的距离
nxt_dist = max(i+nums[i], nxt_dist)
if i == cur_dist:
if cur_dist != length-1:
ans += 1
cur_dist = nxt_dist
if nxt_dist >= length-1:
break
return anshttps://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/
给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
以这种方式修改数组后，返回数组 可能的最大和。
求解思路：
贪心的思路，局部最优：让绝对值大的负数变为正数，当前数值达到最大，整体最优：整个数组和达到最大。
局部最优可以推出全局最优。
那么如果将负数都转变为正数了，K依然大于0，此时的问题是一个有序正整数序列，如何转变K次正负，让 数组和 达到最大。
那么又是一个贪心：
-
局部最优：只找数值最小的正整数进行反转，当前数值可以达到最大；
-
全局最优：整个 数组和 达到最大。
那么本题的解题步骤为：
- 第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
- 第二步：从前向后遍历，遇到负数将其变为正数，同时K--
- 第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完
- 第四步：求和
class Solution:
def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
# 排序
nums = sorted(nums, key=abs, reverse=True)
for i in range(len(nums)):
if k > 0 and nums[i] < 0:
nums[i] = nums[i] * (-1)
k -= 1
if k > 0:
nums[-1] = nums[-1] * ((-1) ** k)
return sum(nums)在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则保证它是唯一的。
求解思路：
首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。
每个加油站的剩余量rest[i]为gas[i] - cost[i]。
i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，起始位置从i+1算起，再从0计算curSum。
如图：
那么为什么一旦[i，j] 区间和为负数，起始位置就可以是j+1呢，j+1后面就不会出现更大的负数？
如果出现更大的负数，就是更新j，那么起始位置又变成新的j+1了。
而且j之前出现了多少负数，j后面就会出现多少正数，因为耗油总和是大于零的（前提我们已经确定了一定可以跑完全程）。
那么局部最优：当前累加rest[j]的和curSum一旦小于0，起始位置至少要是j+1，因为从j开始一定不行。全局最优：找到可以跑一圈的起始位置。
局部最优可以推出全局最优，找不出反例，试试贪心！
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
- 每个孩子至少分配到 1 个糖果。
- 相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
输入：ratings = [1,2,2] 输出：4 解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。
求解思路： 规则定义： 设学生 A 和学生 B 左右相邻，A 在 B 左边；
-
左规则： 当 ratings_B > ratings_A 时，B 的糖比 A 的糖数量多。
-
右规则： 当 ratings_A > ratings_B 时，A 的糖比 B 的糖数量多。
相邻的学生中，评分高的学生必须获得更多的糖果 等价于 所有学生满足左规则且满足右规则。
算法流程：
-
先从左至右遍历学生成绩 ratings，按照以下规则给糖，并记录在 left 中：
-
先给所有学生 1 颗糖；
-
若 ratings_i > ratings_{i-1}，则第 i 名学生糖比第 i - 1 名学生多 1 个。
-
若 ratings_i <= ratings_{i-1}，则第 i 名学生糖数量不变。（交由从右向左遍历时处理。）
-
经过此规则分配后，可以保证所有学生糖数量 满足左规则 。
同理，在此规则下从右至左遍历学生成绩并记录在 right 中，可以保证所有学生糖数量 满足右规则 。
最终，取以上 2 轮遍历 left 和 right 对应学生糖果数的 最大值，这样则 同时满足左规则和右规则，即得到每个同学的最少糖果数量。
复杂度分析：
- 时间复杂度 O(N)： 遍历两遍数组即可得到结果；
- 空间复杂度 O(N)： 需要借用 left，right 的线性额外空间。
参考：https://leetcode.cn/problems/candy/solution/candy-cong-zuo-zhi-you-cong-you-zhi-zuo-qu-zui-da-/
class Solution:
def candy(self, ratings: List[int]) -> int:
n = len(ratings)
left_candy = [1 for _ in range(n)]
right_candy = left_candy[:]
# 从左到右遍历
for i in range(1, n):
# 如果右边的评分大于左边的评分，则右边的孩子多一个糖果
if ratings[i] > ratings[i-1]:
left_candy[i] = left_candy[i-1] + 1
candy_count = left_candy[-1]
# 从右向左遍历
for j in range(n-2, -1, -1):
if ratings[j] > ratings[j+1]:
# 如果左边的评分大于右边的评分，则左边的孩子多一个糖果
right_candy[j] = right_candy[j+1] + 1
candy_count += max(left_candy[j], right_candy[j])
return candy_count在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
示例1：
输入：bills = [5,5,5,10,20] 输出：true 解释： 前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。 第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。 第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。 由于所有客户都得到了正确的找零，所以我们输出 true。
求解思路：
只需要维护三种金额的数量，5，10和20。
有如下三种情况：
- 情况一：账单是5，直接收下。
- 情况二：账单是10，消耗一个5，增加一个10
- 情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5
此时发现，情况一，情况二，都是固定策略，唯一不确定的是情况三。感觉纯模拟就可以了，其实情况三这里是有贪心的。
账单是20的情况，为什么要优先消耗一个10和一个5呢？因为美元10只能给账单20找零，而美元5可以给账单10和账单20找零，美元5更万能！
局部最优：遇到账单20，优先消耗美元10，完成本次找零。
全局最优：完成全部账单的找零。
局部最优可以推出全局最优，并找不出反例，那么就试试贪心算法！
class Solution:
def lemonadeChange(self, bills: List[int]) -> bool:
five, ten = 0, 0
for bill in bills:
if bill == 5:
five += 1
elif bill == 10:
if five < 1:
return False
five -= 1
ten += 1
else:
if ten > 0 and five > 0:
ten -= 1
five -= 1
elif five > 2:
five -= 3
else:
return False
return Truehttps://leetcode.cn/problems/queue-reconstruction-by-height/
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
示例 1：
输入：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]] 是重新构造后的队列。
求解思路：
套路：一般这种数对，还涉及排序的，根据第一个元素正向排序，根据第二个元素反向排序，或者根据第一个元素反向排序，根据第二个元素正向排序，往往能够简化解题过程。
在本题目中，我首先对数对进行排序，按照数对的 0 位置元素降序排序，按照数对的 1 位置元素升序排序。原因是，按照第一个元素进行降序排序，对于每个元素，在其之前的元素的个数，就是大于等于他的元素的数量，而按照第二个元素正向排序，我们希望 k 大的尽量在后面，减少插入操作的次数。
排序完的people： [[7,0], [7,1], [6,1], [5,0], [5,2]，[4,4]]
插入的过程：
- 插入[7,0]：[[7,0]]
- 插入[7,1]：[[7,0],[7,1]]
- 插入[6,1]：[[7,0],[6,1],[7,1]]
- 插入[5,0]：[[5,0],[7,0],[6,1],[7,1]]
- 插入[5,2]：[[5,0],[7,0],[5,2],[6,1],[7,1]]
- 插入[4,4]：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
此时就按照题目的要求完成了重新排列。
class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
# 先按照h维度的身高顺序从高到低排序，确定第一个维度。
# 使用lambda实现，lambda返回的是一个元组：当-x[0](维度h)相同时，再根据x[1](维度k)从小到大排序
people.sort(key=lambda x: (-x[0], x[1]))
que = []
# 将第二个维度k作为插入索引，贪心算法进行插入
for elem in people:
que.insert(elem[1], elem)
return quehttps://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量 没有限制。 弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points ，返回引爆所有气球所必须射出的最小弓箭数 。
求解思路：
局部最优：当气球出现重叠，一起射，所用弓箭最少。全局最优：把所有气球射爆所用弓箭最少。
输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球
为了让气球尽可能的重叠，需要对数组进行排序。那么按照气球起始位置排序，还是按照气球终止位置排序呢？其实都可以！只不过对应的遍历顺序不同。既然按照起始位置排序，那么就从前向后遍历气球数组，靠左尽可能让气球重复。
从前向后遍历遇到重叠的气球了怎么办？如果气球重叠了，重叠气球中右边边界的最小值之前的区间一定需要一个弓箭。
以题目示例：[[10,16],[2,8],[1,6],[7,12]] 为例，如图：
可以看出，第一组重叠气球需要一支箭；气球3的左边界大于了第一组重叠气球的最小右边界，所以再需要一支箭来射气球3。
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
if len(points) == 0:
return 0
points.sort(key=lambda x: x[0])
min_count = 1
for i in range(1, len(points)):
# 如果当前气球的最左边界 大于 前一个气球的最右边界，说明没有重叠区域，则需要增加弓箭射击
if points[i][0] > points[i-1][1]:
min_count += 1
# 原地修改当前气球的左边界
else:
points[i][1] = min(points[i-1][1], points[i][1])
return min_count给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
示例 1:
输入: intervals = [[1,2],[2,3],[3,4],[1,3]] 输出: 1 解释: 移除 [1,3] 后，剩下的区间没有重叠。
按照右边界排序，就要从左向右遍历，因为右边界越小越好，只要右边界越小，留给下一个区间的空间就越大，所以从左向右遍历，优先选右边界小的。
按照左边界排序，就要从右向左遍历，因为左边界数值越大越好（越靠右），这样就给前一个区间的空间就越大，所以可以从右向左遍历。
如果按照左边界排序，还从左向右遍历的话，其实也可以，逻辑会有所不同。
一些同学做这道题目可能真的去模拟去重复区间的行为，这是比较麻烦的，还要去删除区间。题目只是要求移除区间的个数，没有必要去真实的模拟删除区间！
按照右边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数。此时问题转换为求非交叉区间的最大个数。
右边界排序之后，局部最优：优先选右边界小的区间，所以从左向右遍历，留给下一个区间的空间大一些，从而尽量避免交叉。全局最优：选取最多的非交叉区间。局部最优推出全局最优，试试贪心！
这里记录非交叉区间的个数还是有技巧的，如图：
区间 1，2，3，4，5，6 都按照右边界排好序。每次取非交叉区间的时候，都使用 右边界最小的 作为分割点，这样留给下一个区间的空间就越大，所以第一条分割线就是区间 1 结束的位置。
接下来就是找大于区间 1 结束位置的区间，是从区间 4 开始。那有同学问了为什么不从区间 5 开始？因为已经是按照右边界排序的了。接着找大于区间 4 结束位置的区间，找到区间 6，所以一共记录非交叉区间的个数是三个（1、4、6）。总共区间个数为6，减去非交叉区间的个数 3，移除区间的最小数量就是 3。
总结如下难点：
- 难点一：究竟怎么排序，按左边界排还是右边界排。
- 难点二：排完序之后如何遍历。
- 难点三：直接求重复的区间是复杂的，转而求最大非重复区间个数。
- 难点四：求最大非重复区间个数时，需要一个分割点来做标记。
这四个难点都不好想，但任何一个没想到位，这道题就解不了。
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
# 区间数量
num_itvs = len(intervals)
# 按照区间结束端排序
intervals.sort(key=lambda x: x[1])
# 非交叉区间的数量
count = 1
# 以区间结束端作为区间分割点
split_end = intervals[0][1]
for i in range(1, num_itvs):
if split_end <= intervals[i][0]:
count += 1
split_end = intervals[i][1]
return num_itvs - count字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
输入：S = "ababcbacadefegdehijhklij" 输出：[9,7,8] 解释： 划分结果为 "ababcbaca", "defegde", "hijhklij"。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
求解思路：
在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点。可以分为以下两步：
- 统计每一个字符最后出现的位置；
- 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等，则找到了分割点。
如图：
class Solution:
def partitionLabels(self, s: str) -> List[int]:
letter_list = [0] * 26
for i in range(len(s)):
# 统计每一个字符最后出现的位置
letter_list[ord(s[i]) - ord('a')] = i
result = []
left, right = 0, 0
for i in range(len(s)):
right = max(right, letter_list[ord(s[i]) - ord('a')])
if i == right:
result.append(right - left + 1)
left = i + 1
return resultclass Solution:
def partitionLabels(self, s: str) -> List[int]:
lower_letter = [chr(i) for i in range(97, 123)]
letter_hash = dict(zip(lower_letter, [0] * 26))
for idx, elem in enumerate(s):
# 统计每一个字符最后出现的位置
letter_hash[elem] = idx
result = []
left, right = 0, 0
for idx, elem in enumerate(s):
right = max(right, letter_hash[elem])
if idx == right:
result.append(right - left + 1)
left = idx + 1
return result以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi]。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].求解思路：
如果我们按照区间的左端点排序，那么在排完序的列表中，可以合并的区间一定是连续的。如下图所示，标记为蓝色、黄色和绿色的区间分别可以合并成一个大区间，它们在排完序的列表中是连续的：
我们用数组 merged 存储最终的答案。
首先，我们将列表中的区间按照左端点升序排序。然后我们将第一个区间加入 merged 数组中，并按顺序依次考虑之后的每个区间：
如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后，那么它们不会重合，我们可以直接将这个区间加入数组 merged 的末尾；
否则，它们重合，我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点，将其置为二者的较大值。
参考：https://leetcode.cn/problems/merge-intervals/solution/he-bing-qu-jian-by-leetcode-solution/
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda x: x[0])
merged = []
for interval in intervals:
# 如果当前列表为空，或者当前区间与上一个区间不重合，则直接添加
if not merged or merged[-1][1] < interval[0]:
merged.append(interval)
# 否则的话，就可以与上一个区间进行合并
else:
merged[-1][1] = max(merged[-1][1], interval[1])
return merged当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。给定一个整数 n，返回 小于或等于 n 的最大数字，且数字呈 单调递增。
示例 3:
输入: n = 332 输出: 299
求解思路：
局部最优：遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]--，然后strNum[i]给为9，可以保证这两位变成最大单调递增整数。
全局最优：得到小于等于N的最大单调递增的整数。
但这里局部最优推出全局最优，还需要其他条件，即遍历顺序，和标记从哪一位开始统一改成9。
举个例子，数字：332，从前向后遍历的话，那么就把变成了329，此时2又小于了第一位的3了，真正的结果应该是299。从后向前遍历，就可以重复利用上次比较得出的结果了，从后向前遍历332的数值变化为：332 -> 329 -> 299。确定了遍历顺序之后，那么此时局部最优就可以推出全局，找不出反例，试试贪心。
class Solution:
def monotoneIncreasingDigits(self, n: int) -> int:
digits_str = list(str(n))
for i in range(len(digits_str)-1, 0, -1):
if int(digits_str[i]) < int(digits_str[i-1]):
digits_str[i-1] = str(int(digits_str[i-1]) - 1)
digits_str[i:] = '9' * (len(digits_str) - i)
return int("".join(digits_str))