（十四）算法设计思想之“贪心算法”
算法设计思想之“贪心算法”
贪心算法是什么
贪心算法是算法设计中的一种方法
期盼通过每个阶段的局部最优选择，从而达到全局的最优
结果并不一定是最优
LeetCode：455.分饼干
解题思路
局部最优：既能满足孩子，还消耗最少
先将“较小的饼干”分给“胃口最小”的孩子
解题步骤
对饼干数组和胃口数组升序排序
遍历饼干数组，找到能满足第一个孩子的饼干
然后继续遍历饼干数组，找到满足第二、第三、…、n个孩子的饼干
时间复杂度O（n * logN），空间复杂度O(1)
LeetCode：122.买卖股票的最佳时机II
解题思路
前提：上帝视角，知道未来的价格
局部最优：较好就收，见差就不动，不做任何长远打算
解题步骤
新建一个变量，用来统计总利润
遍历价格数组，如果当前价格比昨天高，就在昨天买，今天卖，否则不交易
遍历结束后，返回所有利润之和
时间复杂度O（n ），空间复杂度O(1)
思考题
1、说出贪心算法的套路步骤。
2、贪心算法总能求的最优解吗？为什么？