【四】【算法分析与设计】贪心算法的初见

455. 分发饼干

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

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

示例 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.

提示：

• 1 <= g.length <= 3 * 10(4)

• 0 <= s.length <= 3 * 10(4)

• 1 <= g[i], s[j] <= 2(31) - 1

class Solution {
public:
    int findContentChildren(vector<int>& children, vector<int>& cookies) {
        sort(children.begin(), children.end());
        sort(cookies.begin(), cookies.end());
        int child = 0, cookie = 0;
        while (child < children.size() && cookie < cookies.size()) {
            if (children[child] <= cookies[cookie])
                ++child;
            ++cookie;
        }
        return child;
    }
};

问题的核心是尽可能满足更多孩子的胃口，每个孩子最多能得到一块饼干，每块饼干也只能分给一个孩子，给定一个孩子数组children代表每个孩子的胃口值，一个饼干数组cookies代表每块饼干的大小，求最多有多少孩子能得到饼干满足胃口。

sort(children.begin(), children.end());这行代码将children数组按胃口值从小到大排序。

sort(cookies.begin(), cookies.end());这行代码将cookies数组按饼干大小从小到大排序。

int child = 0, cookie = 0;初始化两个变量child和cookie，分别表示当前考虑到的孩子和饼干的索引。

while (child < children.size() && cookie < cookies.size()) {这个循环继续执行直到所有孩子都被考虑过或所有饼干都被尝试分配。

if (children[child] <= cookies[cookie]) ++child;如果当前饼干的大小能满足当前孩子的胃口，那么这个孩子被满足，移动到下一个孩子。

++cookie;无论当前的饼干是否能满足当前的孩子，都将考虑下一块饼干。

时间复杂度和空间复杂度

时间复杂度：O(nlogn)。主要时间开销来自于排序children和cookies数组，假设children和cookies的长度分别为m和n，那么时间复杂度为O(mlogm + nlogn)。遍历数组的过程时间复杂度为O(m+n)，所以总体时间复杂度为O(nlogn)，这里n是两个数组中较长的那个的长度。

空间复杂度：O(1)。除了输入的数组外，我们只使用了常数空间。

135. 分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。

• 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

示例 1：

输入：ratings = [1,0,2] 输出：5 解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2：

输入：ratings = [1,2,2] 输出：4 解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。 第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

提示：

• n == ratings.length

• 1 <= n <= 2 * 10(4)

• 0 <= ratings[i] <= 2 * 10(4)

class Solution {
public:
    int candy(vector<int>& ratings) {
        int size = ratings.size();
        if (size < 2) {
            return size;
        }
        vector<int> num(size, 1);
        for (int i = 1; i < size; ++i) {
            if (ratings[i] > ratings[i - 1]) {
                num[i] = num[i - 1] + 1;
            }
        }
        for (int i = size - 1; i > 0; --i) {
            if (ratings[i] < ratings[i - 1]) {
                num[i - 1] = max(num[i - 1], num[i] + 1);
            }
        }
        return accumulate(num.begin(), num.end(),0); // std::accumulate 可以很方便地求和
    }
};

定义变量 size 为评分数组 ratings 的长度。

如果 size 小于 2，直接返回 size。因为如果只有一个孩子，那他就是唯一的获得糖果的人，直接返回1；如果没有孩子，返回0。

初始化一个大小与 ratings 相同，值全为1的数组 num。这一步确保了每个孩子至少得到一颗糖果。

第一次遍历：从左到右遍历 ratings。

如果当前孩子（i对应孩子）的评分高于左边的孩子（ratings[i] > ratings[i - 1]），则当前孩子得到的糖果数应该比左边的孩子多一颗（num[i] = num[i - 1] + 1）。

第二次遍历：从右到左遍历 ratings。

如果当前孩子（i-1对应孩子）的评分高于右边的孩子（ratings[i] < ratings[i - 1]），则左边的孩子得到的糖果数应该是其原本的数目和右边孩子的糖果数加一中的较大值（num[i - 1] = max(num[i - 1], num[i] + 1)）。

最后，使用 accumulate 函数对 num 数组进行求和，得到总共需要的糖果数，并返回这个值。accumulate 函数起始值为0，意味着从0开始累加 num 数组中所有元素的值。

accumulate函数

accumulate 函数是 C++ 标准库中 <numeric> 头文件提供的一个非常实用的数值累加函数。它用于计算一个给定范围内所有元素的累加和，或者在提供了自定义操作时，按照该操作进行累加。accumulate 的基本用法是计算序列的总和，但通过自定义加法操作，它也可以用于更复杂的累加操作，如累乘。

基本用法

基础版本的 accumulate 接受三个参数：序列的开始迭代器、结束迭代器和累加的初始值。如果不指定操作，则默认进行加法操作。下面是一个简单的例子：

#include <numeric> // 引入accumulate的头文件
#include <vector>
 
std::vector<int> v = {1, 2, 3, 4, 5};
int sum = std::accumulate(v.begin(), v.end(), 0); // 计算总和

在这个例子中，accumulate 从 0 开始，将 v 中的每个元素相加，计算出总和为 15。

使用自定义操作

accumulate 还允许你指定一个自定义的二元操作函数，来代替默认的加法操作。这个二元操作接受两个参数：累加值（到当前为止的结果）和序列中的当前元素。这使得 accumulate 变得非常灵活，可以实现各种复杂的累加逻辑。

例如，使用 accumulate 来计算一个数列的乘积：

#include <numeric>
#include <vector>
 
std::vector<int> v = {1, 2, 3, 4, 5};
int product = std::accumulate(v.begin(), v.end(), 1, [](int a, int b) {
    return a * b;
});

这里，初始值设为 1（乘法的单位元），并通过一个 lambda 表达式指定乘法为累加操作。最终，product 的值为 120，即 1*2*3*4*5 的结果。

注意事项

accumulate 默认使用加法操作时，累加初始值的类型决定了整个操作的类型。例如，如果初始值为整数，那么即使数组是浮点数，累加结果也会被截断为整数。因此，选择合适的初始值类型是非常重要的。

435. 无重叠区间

给定一个区间的集合 intervals ，其中 intervals[i] = [start(i), end(i)] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

示例 1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]] 输出: 1 解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:

输入: intervals = [ [1,2], [1,2], [1,2] ] 输出: 2 解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

输入: intervals = [ [1,2], [2,3] ] 输出: 0 解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

提示:

• 1 <= intervals.length <= 10(5)

• intervals[i].length == 2

• -5 * 10(4) <= start(i) < end(i) <= 5 * 10(4)

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    if (intervals.empty()) {
        return 0;
    }
    int n = intervals.size();
    sort(intervals.begin(), intervals.end(), [](vector<int> a, vector<int> b) {
        return a[1] < b[1];
    });
    int total = 0, prev = intervals[0][1];
    for (int i = 1; i < n; ++i) {
        if (intervals[i][0] < prev) {
            ++total;
        } else {
            prev = intervals[i][1];
        }
    }
    return total;
 }

检查区间数组是否为空：

if (intervals.empty()) { return 0; }如果区间数组为空，则没有需要移除的区间，直接返回0。

获取区间数组的大小：

int n = intervals.size();这里定义了一个变量 n 来存储区间数组的长度。

按区间结束时间排序：

sort(intervals.begin(), intervals.end(), [](vector<int> a, vector<int> b) { return a[1] < b[1]; });使用标准库函数 sort，通过自定义的比较函数，将区间按照结束时间升序排序。这样做的目的是尽可能让区间不重叠，因为结束得早的区间留给后面的区间的空间就越多。

初始化计数器和前一个区间的结束右端点：

int total = 0, prev = intervals[0][1];初始化需要移除的区间数量 total 为0，并将 prev 设置为第一个区间的结束时间。prev 用于记录当前不重叠区间的最后一个区间的结束时间。

遍历区间数组，确定需要移除的区间数量：

for (int i = 1; i < n; ++i) { if (intervals[i][0] < prev) { ++total; } else { prev = intervals[i][1]; } }从第二个区间开始遍历，如果当前区间的开始时间小于前一个区间的结束时间 prev，说明这两个区间重叠，需要移除一个区间，因此 total 自增1。如果不重叠，更新 prev 为当前区间的结束时间，继续向后比较。

标准库函数sort

C++ 标准库中的 sort 函数是一个非常强大且灵活的排序算法，主要用于对数组或容器内的元素进行排序。它位于 <algorithm> 头文件中。sort 函数可以对一个序列进行默认的升序排序，也可以通过自定义比较函数来指定排序规则。

基本用法

默认情况下，sort 对序列进行升序排序。如果你想对一个数组或者 vector 排序，可以这样使用：

#include <algorithm> // 引入算法库
#include <vector>
 
std::vector<int> v = {4, 2, 5, 3, 1};
std::sort(v.begin(), v.end());

在上述代码中，v.begin() 和 v.end() 分别是容器 v 的起始迭代器和终止迭代器，sort 函数会将 v 中的元素从小到大排序。

自定义比较函数

sort 函数允许你通过自定义比较函数来指定排序规则，这让你能够实现复杂的排序逻辑，比如降序排序或者根据对象的某个属性排序。

自定义比较函数可以是一个普通函数，也可以是一个lambda表达式。比较函数需要接受两个参数（被比较的元素），并返回一个布尔值，指示第一个参数是否应该位于第二个参数之前。

使用普通函数作为比较函数

bool compare(int a, int b) {
    return a > b; // 降序排序
}
 
std::vector<int> v = {4, 2, 5, 3, 1};
std::sort(v.begin(), v.end(), compare);

使用 Lambda 表达式

Lambda 表达式提供了一种便捷的方式来定义临时的比较函数，这在实现简单的自定义排序规则时非常有用：

std::vector<int> v = {4, 2, 5, 3, 1};
std::sort(v.begin(), v.end(), [](int a, int b) {
    return a > b; // 降序排序
});

对象排序

如果你想根据对象的某个属性排序，可以这样做：

struct Person {
    std::string name;
    int age;
};
 
bool compareByAge(const Person& a, const Person& b) {
    return a.age < b.age; // 按年龄升序排序
}
 
std::vector<Person> people = {{"Alice", 30}, {"Bob", 25}, {"Carol", 20}};
std::sort(people.begin(), people.end(), compareByAge);

或者使用 Lambda 表达式：

std::sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
    return a.age < b.age; // 按年龄升序排序
});

结尾

最后，感谢您阅读我的文章，希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点，请随时在评论区留言。

同时，不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中，我将继续探讨这个话题的不同方面，为您呈现更多深度和见解。

谢谢您的支持，期待与您在下一篇文章中再次相遇！