贪心算法 | note

# 贪心算法

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

# 应用场景

# 算法题：分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例 1:

输入: g = [1,2,3], s = [1,1]
输出: 1
解释: 
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。

链接：https://leetcode-cn.com/problems/assign-cookies

解题思路：既能满足孩子，还消耗最少，先将较小的饼干分给胃口最小的孩子。
解题步骤：对饼干数组和胃口数组升序排序；遍历饼干数组，找到能满足第一个孩子的饼干；然后继续遍历饼干数组，找到满足第二、三 .... n 个孩子的饼干；

时间复杂度为 O(n * logn); 空间复杂度：O(1);

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

# 算法题：买卖股票的最佳时机 II

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

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

链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii

解题思路：局部最优：见好就收，不做任何长远打算；
解题步骤：新建一个变量，用来统计总利润。遍历价格数组，如果当前价格比昨天高，就在昨天买，今天卖，否则就不交易；遍历结束，返回利润之和；

时间复杂度为 O(n); 空间复杂度：O(1);

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let profit = 0;
    prices.forEach((item, i) => {
         // 当前价格比前一天高-昨天买今天卖
        if (item > prices[i - 1]) {
            profit += item - prices[i - 1];
        }
    })
    return profit;
};

阅读量：

# 贪心算法

# 应用场景

# 算法题：分发饼干

# 算法题：买卖股票的最佳时机 II

评 论：

评论：