算法设计思想-贪心算法

1. 是什么

• 通过每个阶段的局部最优选择，从而达到全局的最优。
• 结果并不一定是最优。

2. 场景

2.1. 分饼干 leetCode 455

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

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

2.2. 买卖股票的最佳时机 leetCode: 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;
};