455. 分发饼干

image.png

尽量满足多的孩子，就得尽可能的把小饼干发给胃口小的孩子，因此，可以对饼干和孩子排序，将小饼干发给小孩子，如果最小的饼干满足不了当前孩子，再将稍大一点的饼干给他试试，如果当前饼干满足要求，再尝试将更大一点的饼干给下一个孩子。

局部最优解：大饼干喂给大的或者小饼干喂给小的
全局最优解：尽可能满足最多的小孩

小饼干喂给小的

  1. class Solution {
  2. public:
  3.     int findContentChildren(vector<int>& g, vector<int>& s) {
  4.         sort(g.begin(), g.end());
  5.         sort(s.begin(), s.end());
  6.         int child = 0, cookie = 0; // 当前处理的孩子和饼干索引
  7.         while(child < g.size() && cookie < s.size()) {//饼干和孩子都没处理完
  8.             if (g[child] <= s[cookie]) child++; // 小饼干满足胃口，处理下一个孩子
  9.             cookie++; // 无论是否满足胃口，都要处理下一块饼干
  10.         }
  11.         return child;
  12.     }
  13. };

大饼干喂给大的

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int child = 0, cookie = s.size() - 1; // 当前处理的孩子和饼干索引
        for (int i = g.size() - 1; i >= 0; i--) {
            if (cookie >= 0 && s[cookie] >= g[i]){
                child++;
                cookie--;
            }
        }
        return child;
    }
};

135. 分发糖果

image.png
贪心策略，保证每个孩子比左边右边比自己分低的孩子糖果多
局部最优：

  • 每个孩子比它左边相邻的分低孩子糖多
  • 每个孩子比它右边相邻的分低孩子糖多

全局最优：

  • 每个孩子至少分配到 1 个糖果。
  • 评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。

用两趟循环，一趟从左往右遍历，评分高的孩子都比左边孩子有更多的糖果；一趟从右往左遍历，评分高的孩子都比右边孩子有更多的糖果

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        if (n < 2) return n;
        vector<int> nums(n, 1); // 记录每个孩子的糖果数，初始都发1颗

        // 从左往右遍历
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) { // 左边评分高于右边
                nums[i] = nums[i - 1] + 1; //多一颗就行了，也算是贪心的策略
            }
        }
        // 从右往左遍历, 只有从右往左遍历才能利用已经更新的结果（右边已经处理过）来更新左边的孩子
        for (int i = n - 1; i > 0; i--) {
            if (ratings[i] < ratings[i - 1]) { // 右边评分高于左边
                nums[i - 1] = max(nums[i - 1], nums[i] + 1); // 如果本来就糖多，则不处理，否让TA糖比右边多一颗
            }
        }

        return accumulate(nums.begin(), nums.end(), 0);
    }
};