贪心算法例题与答案

贪心算法是一种最优化算法，通过优先考虑当前局部最优解来达到全局最优解的目的。它的核心思想是在每一步选择中都选择当前状态下最优（即局部最优）的解，从而导致结果最终也是最优（即全局最优）。本文将通过具体例题和答案的分析，从多个角度来介绍贪心算法。

例题1：买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意：不能在买入股票前卖出股票。

示例：

输入: [7,1,5,3,6,4]

输出: 5

解释: 在第2天（股票价格 = 1）的时候买入，在第5天（股票价格 = 6）的时候卖出，最大利润只能是5。

答案1：从低点买入高点卖出

贪心的核心理念是要优先考虑当前的最优解。因此在这个例子中，我们需要找到一个最低点买入，然后在未来找到一个当前价值高于此价格的点来卖出，这样我们才能在这次交易中得到最大的收益。在答案中，我们使用了一个变量来跟踪当前最低的点和当前最大的利润。我们一次遍历数组来找到价格最低的点，并且在以后的计算中，只有当当前股票价格高于已知的最低价格时，我们才更新最大利润。

def maxProfit(prices):

lowest = float('inf') # 初始化为正无穷大

max_profit = 0

for price in prices:

if price < lowest:

lowest = price

else:

max_profit = max(max_profit, price - lowest)

return max_profit

时间复杂度：O(n)

例题2：分配饼干

题目描述：每个孩子都有一个满足度，每个饼干有一个大小，只有饼干的大小大于一个孩子的满足度，该孩子才会获得满足。求解最多可以获得满足的孩子数量。

我们的贪心策略应该是尽量保证大饼干分给大需求的小朋友，小饼干分给小需求的小朋友。这样可以让更多的孩子得到满足。

因此，我们需要将孩子需求和饼干大小都从小到大排序。然后使用两个指针分别指向孩子和饼干数组的开头，依次比较大小，如果饼干大小大于等于孩子需求，那么当前孩子的需求被满足，两个指针都向后移动一位，否则说明当前饼干不能满足当前孩子的需求，扫描下一个饼干。

def findContentChildren(g, s) -> int:

g.sort()

s.sort()

i, j = 0, 0

while i < len(g) and j < len(s):

if s[j] >= g[i]:

i += 1

j += 1

return i

时间复杂度：O(nlogn)

在贪心算法中，我们总是希望能够找到一种局部最优的方案，并用它来推导全局最优解。在解决问题时，通常需要思考自己所采用的贪心策略是否正确，具体问题具体分析。