## 贪心算法是什么？ > 摘自：[五大常用算法之三贪心算法](https://www.cnblogs.com/xsyfl/p/6938642.html) 贪心算法是指：在每一步求解的步骤中，它要求“贪婪”的选择最佳操作，并希望通过一系列的最优选择，能够产生一个问题的（全局的）最优解。 贪心算法每一步必须满足一下条件： + 可行的：即它必须满足问题的约束。 + 局部最优：他是当前步骤中所有可行选择中最佳的局部选择。 + 不可取消：即选择一旦做出，在算法的后面步骤就不可改变了。 **有些情况，贪心算法确实可以给出最优解，然而，还有一些问题并不是这种情况。对于这种情况，我们关心的是近似解，或者只能满足于近似解，贪心算法也是有价值的。** ## LeetCode例题 ### 122.Best Time to Buy and Sell Stock II（买卖股票的最佳时机 II） 本题隐含着一个思路：如果每次买卖都在最低点和最高点，那么多买多卖一定就赚的最多。 也就是说，只要我们在短期内的最低价买入，最高价卖出就可以获得最大利润 转换成图形，那就是在极小值（山谷）买入，极大值（山峰）卖出即可。如下图（图来自[力扣](https://leetcode-cn.com)）  本题有三种解题思路。暴力算法不考虑。 #### 峰谷法 寻找极大和极小值，在每个极大和极小值买入和卖出。 ```java class Solution { public int maxProfit(int[] prices) { int i = 0; int valley = prices[0]; int peak = prices[0]; int maxprofit = 0; while (i < prices.length - 1) { while (i < prices.length - 1 && prices[i] >= prices[i + 1]) //寻找最小值 i++; valley = prices[i]; while (i < prices.length - 1 && prices[i] <= prices[i + 1]) //寻找最大值 i++; peak = prices[i]; maxprofit += peak - valley; } return maxprofit; } } ``` 注意上面的算法只使用了一个游标i，同时寻找山谷和山峰。因为山谷和山峰之间存在前者一定先于后者出现的关系 --- 对上面的算法进行优化。 这题里面不需要知道每次买卖的时机，所以可以省略记录山峰和山谷的步骤 再次抽象化本题的特点，可以发现，其实只要明天的值大于今天的值，那么我在这两天持有股票即可获利。 那么解决方法简化为 ```java class Solution { public int maxProfit(int[] prices) { int maxProfit = 0; for(int x = 0; x < prices.length; x++){ if(x + 1 < prices.length && prices[x] <= prices[x + 1]){ //如果市值是增长的，那么持有股票 maxProfit += prices[x + 1] - prices[x]; } } return maxProfit; } } ``` ### 455.Assign Cookies（分发饼干） 本题的贪心思路在于：每次分发饼干的时候，分发剩余饼干中尺寸最小的那个饼干，去满足一个胃口刚好适合这个饼干的孩子 如果是这样一个分发思路的话，那么大尺寸的饼干可以去满足大胃口的孩子 如果不是的话，很可能大尺寸的饼干分给了一个小胃口的孩子，那么大胃口的孩子就有可能没有办法被满足 算法如下： ```java class Solution { public int findContentChildren(int[] g, int[] s) { //g：孩子胃口，s：饼干尺寸 //先对数组进行由小到大排序 //保证每次分发的饼干是剩余饼干里最小的 //也保证从最小胃口的孩子开始分发 Arrays.sort(g); Arrays.sort(s); int i = 0, j = 0; while(i < g.length && j < s.length){ if(g[i] <= s[j]){ i++; } j++; } return i; } } ```