在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。

一、分发饼干

力扣455
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

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

class Solution {
    //用尽量小的饼干去满足小需求的孩子，这样可以尽可能多的满足多个孩子
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int gi = 0;
        int si = 0;
        while (gi < g.length && si < s.length) {
            if (g[gi] <= s[si]) {          //当前的饼干符合当前孩子的需求
                gi++;
            }
            si++;       //饼干使用过一次就要被放弃，找下一个更大的饼干，是否满足孩子需求
        }
        return gi;
    }

    //官方
    public int findContentChildrenByOfficial(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int numOfChildren = g.length
        int numOfCookies = s.length;
        int count = 0;
        for (int i = 0, j = 0; i < numOfChildren && j < numOfCookies; i++, j++) {
            while (j < numOfCookies && g[i] > s[j]) {
                j++;        //孩子食量大于饼干，要去要一直去找到那个符合当前孩子吃的
            }
            if (j < numOfCookies) {//进入这里的条件是j < numOfCookies && g[i] > s[j]即:当前孩子得到了分配
                count++;
            }
        }
        return count;
    }
}

二、买卖股票最佳时机

力扣121
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length <= 1)
            return 0;
        int min = prices[0];                //第一天的就是默认的最低价
        int receive = 0;                        //第一天收益默认是0
        for (int i = 1; i < prices.length; i++) {
            receive = Math.max(receive, prices[i] - min);//计算当天的利润和原来的利润作比较，取最大值
            min = Math.min(min, prices[i]); //找股票最低价
        }
        return receive;
    }

    public int maxProfitByOfficial(int[] prices) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minprice) {
                minprice = prices[i];
            } else if (prices[i] - minprice > maxprofit) {
                maxprofit = prices[i] - minprice;
            }
        }
        return maxprofit;
    }
}