前言

贪心算法，算法结构一如其名，以局部最优解，进行小范围的最优累加！

贪心算法的核心就是要找出问题的贪心策略，贪心策略的本质逻辑就是每一次都选择当前的最优解，直到得出全局的最优解，但是每一次的局部最优解不能和最终的全局最优解划上等号，不从整体考虑所有的可能，每次都是采用局部最优，不回溯，所以有时无法得出最优解，这也就是贪心策略的缺点。

此次题目依旧来自leecode。

1. 贪心算法

1.1 leecode题目-买卖股票的最佳时机 II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润

例子：

输入：prices = [7,1,5,3,6,4]

输出：7

解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
     总利润为 4 + 3 = 7 。

1.2 分解题目

• 可在同一天买进、卖出，意味着当第二天价格高于第一天的时候，可以选择当天卖出，也就是最小利润为0，不会出现负值利润
• 不是每天必须出售，所以，当为第n天买入，发现第n+1天价格大于第n天，则利润累加，发现第n+2天价格大于第n+1天，则利润累加，发现第n+3天价格小于第n-2天，则不累加；

1.3 解题思路

遍历循环，由于要对比两个元素的差值，所以，默认循环从索引1的位置开始，设定初始利润为0，则判断第i天与第 i -1 天销售价格的差额是否大于0，如果大于0，则累加利润，如果小于等于0，则意味着当天买进并卖出。

1.4 代码

function greedy(prices) {
  let length = prices.length;
  let num = 0;
  for (let i = 1; i < length; i++) {
    num += Math.max(0, prices[i] - prices[i - 1]);
  }
  return num;
}
greedy([7, 1, 5, 3, 6, 4]);

输出值num为7；

1.5 复杂度分析

• 时间复杂度：O(n)，其中n 为数组的长度。我们只需要遍历一次数组即可。
• 空间复杂度：O(1)。只需要常数空间存放若干变量。

1.6 缺点举例

这里举一个例子来说明贪心策略，就是找零钱的例子。

假如你有25分、10分、5分、1分的硬币，现在要找给客人41分零钱，如何办到找的硬币个数最少？

运用贪心策略，要达到硬币个数最少，那么每一次就尽量找硬币面值最大的，步骤如下：

选择25分硬币，还剩下16分；
选择10分硬币，还剩下6分；
选择5分硬币，还剩下1分；
选择1分硬币，找完。
最后41分零钱需要找4个硬币，分别是25、10、5、1 各一个。这个解是一个最优解了。

当把题目给做一下调整，假如你有25分、20分、5分、1分硬币，现在要找给客人41分零钱，如何办到找的硬币个数最少？

这里还运用贪心策略，步骤如下：

选择25分硬币，还剩下16分；
选择5分硬币，还剩下11分；
选择5分硬币，还剩下6分；
选择5分硬币，还剩下1分；
选择1分硬币，找完。
最后41分零钱需要找5个硬币，25分一个，5分有3个，1分有1个。但是这个并不是最优解。最优的解应该是20分有两个，1分一个，总共三个硬币就可以了。

2.总结

由上面两个找零钱的例子，可以总结为只看到眼前的利益，走一步看一步，看不到长远的利益。

所以一般来说，贪心算法可以作为辅助算法，不能做严格的算法。

寄语

贪婪是七宗罪之一，执着与眼前的利弊，只会让你越陷越深