贪心
455分发饼干
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
注意：
你可以假设胃口值为正。
一个小朋友最多只能拥有一块饼干。
示例 1:
输入: [1,2,3], [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。
示例 2:
输入: [1,2], [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.
题解
为了满足最多的孩子，应该尽量让胃口小的吃小饼干， 把胃口小的先满足。将孩子胃口，和饼干都升序排列，这里还用了两个指针。
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g.sort()
s.sort()
i,j = 0,0
count = 0
while True:
if i>=len(g) or j>=len(s):
break
if g[i]<=s[j]:
count += 1
i += 1
j += 1
return count
435无重叠区间
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意:
可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
示例 1:
输入: [ [1,2], [2,3], [3,4], [1,3] ]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:
输入: [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
输入: [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
题解
在每次选择中，区间的结尾最为重要，选择的区间结尾越小，尽可能留给后面的区间的空间越大，那么后面能够选择的区间个数也就越大。
按区间的结尾进行排序，每次选择结尾最小，并且和前一个区间不重叠的区间。
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
if not intervals:
return 0
intervals.sort(key=lambda x: x[1]) # 注意这里是按照第二个元素来排序
count = 0
end = intervals[0][1] # 初始化end
for i in range(1,len(intervals)):
if intervals[i][0] < end:
count += 1
else:
end = intervals[i][1] # 更新end
return count
402移掉K位数字
给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
注意:
num 的长度小于 10002 且 ≥ k。
num 不会包含任何前导零。
示例 1 :
输入: num = "1432219", k = 3
输出: "1219"
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。
示例 2 :
输入: num = "10200", k = 1
输出: "200"
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
示例 3 :
输入: num = "10", k = 2
输出: "0"
解释: 从原数字移除所有的数字，剩余为空就是0。
这道题主要思路：当指针指向的数比左边的数小，那么舍弃左边的数，在删除数字时应该从左向右迭代，这样的数整体最小。这里用到栈的思想，也就是一个列表。
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
numStack = []
for i in num:
while k and numStack and numStack[-1]>i: #这里循环是为了将i与栈内的所有数进行比较，保证整体最小。
numStack.pop()
k -= 1
numStack.append(i)
numStack = numStack[:-k] if k else numStack
return ''.join(numStack).lstrip('0') or '0'
452用最少数量的箭引爆气球
在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以y坐标并不重要，因此只要知道开始和结束的x坐标就足够了。开始坐标总是小于结束坐标。平面内最多存在104个气球。
一支弓箭可以沿着x轴从不同点完全垂直地射出。在坐标x处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。
Example:
输入:
[[10,16], [2,8], [1,6], [7,12]]
输出:
2
解释:
对于该样例，我们可以在x = 6（射爆[2,8],[1,6]两个气球）和 x = 11（射爆另外两个气球）。
这道题也是计算区间重叠的个数，和上面那道差不多。按每个区间end升序排列。
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
if len(points)==0:
return 0
points.sort(key=lambda x:x[1])
end = points[0][1]
count = 1
for i in range(1,len(points)):
if points[i][0]<=end:
continue
else:
end = points[i][1]
count+=1
return count
406. 根据身高重建队列
假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。
注意：
总人数少于1100人。
示例
输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
让我们从最简单的情况下思考，当队列中所有人的 (h,k) 都是相同的高度 h，只有 k 不同时，解决方案很简单：每个人在队列的索引 index = k。
即使不是所有人都是同一高度，这个策略也是可行的。因为个子矮的人相对于个子高的人是 “看不见” 的，所以可以先安排个子高的人。
上图中我们先安排身高为 7 的人，将它放置在与 k 值相等的索引上；再安排身高为 6 的人，同样的将它放置在与 k 值相等的索引上。
该策略可以递归进行：
- 将最高的人按照 k 值升序排序，然后将它们放置到输出队列中与 k 值相等的索引位置上。
- 按降序取下一个高度，同样按 k 值对该身高的人升序排序，然后逐个插入到输出队列中与 k 值相等的索引位置上。
- 直到完成为止
在python里直接用list.insert(index, i)在Index处插入。最高的人中，肯定有一个人排他前面人数是0，所以我们这里插入第一个肯定是[最高的身高，0]这样
class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
if len(people)<2:
return people
result = []
people.sort(key=lambda x:(-x[0],x[1]))
for i in people:
result.insert(i[1], i)
return result
121. 买卖股票的最佳时机
121
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
只要记录前面的最小价格，将这个最小价格作为买入价格，然后将当前的价格作为售出价格，查看当前收益是不是最大收益。
查看评论后，把它看作DP问题理解起来简单点。
假设当前在第 i 天，令 minPrice 表示前 i-1 天的最低价格；令 maxProfit 表示前 i-1 天的最大收益。那么考虑第 i 天的收益时，存在两种情况：
- 在第 i 天卖出。很显然，想要获得最大收益，应该在前 i-1 天中价格最低的时候买入，即此时的收益为：prices[i] - minPrice。（可能会出现负数，但是没关系）
- 不在第 i 天卖出。那么第 i 天的最大收益就等于前 i -1 天中的最大收益
状态转移方程为：第 i 天最大收益 = max( 在第 i 天卖出的所得收益 , 前 i-1 天的最大收益)
题解
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices)==0:
return 0
Min = prices[0]
Max = 0
for i in range(1,len(prices)):
temp = prices[i] - Min
Max = max(Max, temp)
Min = min(Min, prices[i])
return Max
贪心做法
只允许一笔交易，在从左往右扫描数组的过程中，保存当前的最小值，结果就是ans = max(ans, price[i]-Min)，保证ans时刻保存了当前最大收益。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices)==0:
return 0
Min, ans = prices[0], 0
for i in range(len(prices)):
if Min>=prices[i]:
Min = prices[i]
continue
else:
ans = max(ans, prices[i] - Min)
return ans
188. 买卖股票的最佳时机 IV（这类题通解）
参考LeetCode
763. 划分字母区间
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。
示例 1:
输入: S = "ababcbacadefegdehijhklij"
输出: [9,7,8]
解释:
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
对于遇到的每一个字母，去找这个字母最后一次出现的位置，用来更新当前的最小区间。参考
定义数组 last[char] 来表示字符 char 最后一次出现的下标。定义 anchor 和 j 来表示当前区间的首尾。如果遇到的字符最后一次出现的位置下标大于 j， 就让 j=last[c] 来拓展当前的区间。当遍历到了当前区间的末尾时(即 i==j )，把当前区间加入答案，同时将 start 设为 i+1 去找下一个区间。
class Solution(object):
def partitionLabels(self, S):
last = {c: i for i, c in enumerate(S)} # 构建一个字典来保存每个字符最后一次出现位置，很巧妙。
j = anchor = 0
ans = []
for i, c in enumerate(S):
j = max(j, last[c])
if i == j:
ans.append(i - anchor + 1)
anchor = i + 1
return ans