贪心算法概述
贪心算法（Greedy Algorithm）是一种常见的算法思想，也是算法设计中常用的一种方法。一般来说，贪心算法是指在每一步选择中都采取当前状态下最好或最优（即最有利）的选择，从而导致结果是全局最优或者是最优近似解的算法思想。
贪心算法在实际应用中非常广泛，例如最小生成树、最短路径、背包问题等都可以采用贪心算法进行求解。此外，贪心算法还可以用作其他算法的优化策略，例如在排列组合问题中，先使用贪心算法来过滤掉不必要的枚举情况，可以大幅度降低计算时间。
贪心算法的使用方法
贪心算法一般包含以下几个步骤：
- 将问题转化为适合使用贪心算法解决的子问题。
- 对每个子问题进行贪心选择，确定每个子问题的局部最优解。
- 将每个子问题的解合并，得到原问题的解。
为了完整阐述贪心算法的使用方法，下面针对两种典型的问题进行详细的说明。
1. 买卖股票的最佳时机
给定一个数组，它的第i个元素是一支给定股票第i天的价格。设计一个算法来求最大利润。注意你不能在买入股票前卖出股票。
示例1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第二天股票价格为1时买入，在第五天股票价格为6时卖出。最大利润为6-1 = 5。
示例2：
输入：[7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 即最大利润为0。
思路：
股票买卖的问题是一个典型的贪心问题。我们只需要在股票价格已知的前提下，判断当天的股票价格是否比昨天的股票价格高，如果是则把当天股票卖出并在当天买入，最后累加所有交易后的利润即可。
代码实现：
def maxProfit(prices):
profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i-1]:
profit += prices[i] - prices[i-1]
return profit
过程演示：
假设股票价格数组为：[7, 1, 5, 3, 6, 4]
第一天不买入，第二天价格为1，第二天买入。
第三天价格为5，第三天卖出。
第四天价格为3，不卖出。
第五天价格为6，第五天卖出。
第六天价格为4，不卖出。
最终收益为 5。
2. 分发饼干
假设你是一位很棒的家长，想要给你的孩子们一些饼干。但是，每个孩子最多只能给一块饼干。对于每个孩子i，都有一个胃口值gi，这里给出一个数组代表他们的胃口度量。你有一些饼干，每块都有一种大小si，如果si>=gi，我们可以将饼干分配给孩子i，这个孩子会得到满足，并且你会得到1的满足度。你最多可以给一个孩子分配一块饼干。求解最多可以得到几个满足度？
示例1：
输入：[1,2,3], [1,1]
输出：1
解释：你有两块大小为1的饼干，如果你把它们分别分配给这两个孩子，他们都只能得到1分满足。所以你应该输出1。
示例2：
输入：[1,2], [1,2,3]
输出：2
解释：你有两个孩子和三块小饼干，首先给有更高胃口值的孩子分配饼干。对于第0个孩子，你能给他分配大小为1的饼干，对于第1个孩子，你能给他分配大小为2的饼干，这个孩子会得到满足。所以你最多可以得到2个满足度。
思路：
问题可以转化为在给定胃口和饼干大小的情况下，如何选择合适的饼干使得能够满足更多的孩子。为了达到这个目的，我们可以首先把两个数组进行排序，然后从胃口和饼干大小最小的孩子开始，依次分配饼干，如果能正好满足孩子，就累加满足度，并且继续分配后面更大的孩子和饼干，直到全部分配完毕。
代码实现：
def findContentChildren(g, s):
g.sort()
s.sort()
i, j, res = 0, 0, 0
while i < len(g) and j < len(s):
if g[i] <= s[j]:
res += 1
i += 1
j += 1
else:
j += 1
return res
过程演示：
假设孩子们的胃口值为 [1, 2, 3]，而你有两个饼干，大小分别为 [1, 1]。
第一步，先把孩子们的胃口值数组和饼干大小数组排序：
g = [1, 2, 3]
s = [1, 1]
第二步，从第一个孩子和第一个饼干开始，比较胃口和饼干大小，如果饼干大小>=孩子的胃口，则满足孩子的胃口，同时满足度+1，并且继续比较两个数组中更大的孩子和饼干：
g = [2, 3]
s = [1]
第三步，重复第二步，直到孩子数组或饼干数组全部分配完毕：
g = [3]
s = []
最终，我们找到了两个孩子满足了他们的胃口，因此满足度为 2。
在上述示例中，我们可以看出，贪心算法对于这种具有“最优子结构”的问题非常有效，可以快速求解最优解。但是需要注意的是，使用贪心策略并不代表一定能够求解最优解，对于一些不符合贪心策略的问题，需要使用其他算法进行求解。