455. Assign Cookies.md

LeetCode 455. Assign Cookies

给定一群孩子的饥饿度和一堆饼干的大小，当饼干的大小大于等于孩子的饥饿度时，该孩子吃饱了。试问，最多有多少孩子能吃饱？

思路——贪心问题-分配孩子

全局最优：尽可能让最多的孩子吃饱

局部最优：用当前最小的饼干喂给胃口小的

有若干种分配方法，比如从饥饿度最低的开始分配和饥饿度最高的孩子开始分配。由于饼干是有限的且大小固定的，为了让尽可能多的孩子吃饱，每次都让最容易吃饱的孩子先吃可以满足它的饼干，这样可以尽可能多的让孩子们吃饱

先将饼干和孩子都做排序，然后从小到大遍历，争取为每一个孩子都能找到符合他胃口的最小的饼干

代码

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int numOfChildren = g.length, 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) {
                count++;
            }
        }
        return count;
    }
}

更简略一些的版本：

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int child = 0, cookie = 0;
        while (child < g.length && cookie < s.length) {
            if (g[child] <= s[cookie]) child++;
            cookie++;
        }
        return child;
    }
}

时间复杂度： O(mlogm+nlogn)， m和n分别是数组g和s的长度，主要是排序的时间消耗，遍历只需O(m+n)

空间复杂度： O(logm+logn)，额外空间消耗是排序时的

思考

实际上，通过贪心算法转换为：两个有序数组，比较数组b大于数组a的元素个数(即遍历a，在b中找到所有比a大的元素），或者再抽象，就是同时用两个指针遍历两个列表（数组，链表）的问题。

框架

int i = 0, j = 0; // 初始化

while (i < a.length && j < b.length) {
    // 访问，满足条件的操作
    if (a[i] < b[j]) i++; 
    j++;
}

return i;

思路 -分配饼干-先用大饼干喂给胃口大的人

同样先排序，但是和之前相反，尽量为每一个大饼干都找到一个当前最大胃口的孩子

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int numOfChildren = g.length, numOfCookies = s.length;
        int cnt = 0;
        for (int i = numOfChildren - 1, j = numOfCookies - 1; i >= 0 && j >= 0; i--) {
            if (g[i] <= s[j]) {
                cnt++;
                j--;
            }
        }
        return cnt;
    }
}