贪心算法

概念

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

LeetCode：455.分饼干

解题思路

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

解题步骤

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

/**
 * @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++
        }
    })
    return i
};

455.发饼干
时间复杂度 O(nlogN) // 排序nLogN 遍历n
空间复杂度 O(1)

LeetCode：122.买卖股票的最佳时机

解题思路

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

解题步骤

• 新建一个变量，用来统计总利润
• 遍历价格数组，如果当前价格比昨天高，就在昨天买，今天卖，否则就不交易。

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let profix = 0
    for (let i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i -1]) {
            profix += prices[i] - prices[i - 1]
        }
    }
    return profix
};

122.买卖股票
时间复杂度 O(n)
空间复杂度 O(1)