455. Assign Cookies.md

455. Assign Cookies

思路

贪心。从最小饼干开始分配直到无法分配。
先将g和s从小到大排序，孩子和饼干分别用下标i和j，i和j都从0开始:

• 若g[i] > s[j]，即此时的最小饼干j无法满足此时要求最少的孩子i，应该尝试下一个饼干j+1；
• 若g[i] <= s[j]，即此时的最小饼干能满足此时要求最少的孩子i，应该将j分配给i。i++以处理下一个孩子，j++以处理下一块饼干。

时间复杂度O(n)。

C++

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int i = 0, j = 0, res = 0;
        while(i < g.size() && j < s.size()){
            while(j < s.size() && g[i] > s[j]) j++;
            if(j++ < s.size()) res++;
            i++;
        }
        return res;
    }
};