算法（四）贪心算法

1. 简介

• 贪心算法是算法设计的一种方法
• 全盘通过每个阶段的局部最优选择，从而达到全局的最优
• 结果并不一定是最优

2. LeetCode题

455. 分发饼干

解题思路：

• 局部最优：既能满足孩子，还消耗最少
• 先将“较小的饼干”分给“胃口最小”的孩子

解题步骤：

• 对饼干数组和胃口数组升序排序
• 遍历饼干数组，找到能满足第一个孩子的饼干
• 然后继续遍历饼干数组，找到满足第二、三、……、n个孩子的饼干

var findContentChildren = function (g, s) {
    const sortFunc = (a, b) => {
        return a - b;
    }
    g.sort(sortFunc);
    s.sort(sortFunc);
    let i = 0;
    s.forEach(n => {
        if (n >= g[i]) {
            i++
        }
    })
    return i;
};

122. 买卖股票的最佳时机（二）

解题思路：

• 前提：上帝视角，知道未来的价格
• 局部最优：见好就收，见差就不动，不做任何长远打算

解题步骤：

• 新建一个变量，用来统计总利润
• 遍历价格数组，如果当前价格比昨天高，就在昨天买，今天卖，否则就不交易
• 遍历结束后，返回所有利润之和

var maxProfit = function (prices) {
    let profit = 0;
    for (let i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1]) {
            profit += prices[i] - prices[i - 1];
        }
    }
    return profit;
};