贪心算法

贪心算法，又名贪婪法，是寻找 最优解问题 的常用方法。
这种方法模式一般将求解过程分成 若干个步骤，但每个步骤都应用贪心原则，选取当前状态下 最好/最优的选择 （局部最有利的选择），并以此希望最后堆叠出的结果也是最好/最优的解。

例题

392. 判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，”ace”是”abcde”的一个子序列，而”aec”不是）。 :::info 示例 1:
s = “abc”, t = “ahbgdc”
返回 true.
示例 2:
s = “axc”, t = “ahbgdc”
返回 false. :::

思路

通过双指针，将指针_i_指向_s_字符串，指针_j_指向_t_字符串.
不断遍历t中元素，当遇到t[j]与s[i]相等时，使_i_加一。
遍历结束后，当i等于s长度，返回true；否则返回false.

var isSubsequence = function(s, t) {
    const l1 = s.length;
    const l2 = t.length;
    if (!l1) return true;
    let i = 0;
    for (let j = 0; j < l2; j++) {
        if (s[i] === t[j]) {
            i++;
        }
        if (i === l1) return true;
    }
    return false;
};

455. 分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。 :::info 示例 1:
输入: g=[1,2,3], s=[1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。

示例 2:
输入: g=[1,2], s=[1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2. :::

思路

先将数组s、g都进行排序，然后采用双指针。
指针i指向数组g，指针j指向数组s。当s[j] >= g[i]时，记录数加一，两指针同时前进；否则指针j前进。
当两指针中的任何一个到达终点后，结束遍历。

var findContentChildren = function(g, s) {
    const gl = g.length, sl = s.length;
    let count = 0;
    if (!sl) return count;
    g.sort((a, b) => a - b);
    s.sort((a, b) => a - b);
    let i = 0, j = 0;
    while (i < gl && j < sl) {
        if (g[i] <= s[j]) {
            i++;
            j++;
            count++
        } else {
            j++;
        }
    }
    return count;
};

122. 买卖股票的最佳时机 II

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票） :::info 示例1：
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。 :::

思路

贪心算法，只要第二天的价格比第一天高，就选择今天买入明天卖出。

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