贪心

一、概念定义

所谓贪心，总是做出在当前看来是最好的选择。也就是说，不从整体最优上进行考虑，算法得到的是在某种意义上的局部最优解。

比如，对于一个全是正整数的数组，我要找到其中两个数，使得它们的乘积最大，毫无疑问，一定是取最大和次大的两个数进行相乘，得到的结果最大。这个就是贪心思想。

贪心是一种抽象的算法，需要的不仅仅是积累，往往还有灵光一现。

二、例题分析

1、最大乘积差

int cmp(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}
int maxProductDifference(int* nums, int numsSize){
    qsort(nums, numsSize, sizeof(int), cmp);	//先对数组进行排序
    return nums[numsSize - 1] * nums[numsSize - 2] - nums[0] * nums[1];	//利用贪心，直接取最大的两个数下标作为 w 和 x，最小的两个数下标作为 y 和 z
}

2、三角形的最大周长

int cmp(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}
int largestPerimeter(int* nums, int numsSize){
    qsort(nums, numsSize, sizeof(int), cmp);
    for(int i = numsSize - 1; i >= 2; i--) {
        if(nums[i] < nums[i-1] + nums[i-2]) 	//利用三角形两边之和大于第三边的性质，假设小的两条边为 a 和 b，大的那条为 c，那么必须满足如下等式才能满足它是一个三角形： a + b > c
            return nums[i] + nums[i-1] + nums[i-2];
    }
    return 0;
}

这个问题要求最大的三角形周长，那么势必是最大的那条边 c 越大越好，所以我们可以枚举将所有的边按照递增排序，然后逆序枚举最大的那条边 c，去剩下的边里找小的两条边，最好的情况肯定是比 c 小的最大和次大边最优，如果这两条边都不能满足上述不等式，剩下的边也就肯定也不满足了，所以只需要一个循环即可解决问题。

3、分发饼干

int cmp(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}

int findContentChildren(int* g, int gSize, int* s, int sSize) {
    int m = gSize, n = sSize;
    qsort(g, m, sizeof(int), cmp);
    qsort(s, n, sizeof(int), cmp);	//分别对 胃口值 和 饼干 都进行递增排序
    int count = 0;
    for (int i = 0, j = 0; i < m && j < n; i++, j++) {	//然后将两个游标都指向 胃口值 和 饼干 的开头
        while (j < n && g[i] > s[j]) {  //不满足，饼干 的游标往后移动一格，寻找更加容易满足条件的解，直到 饼干 或者 胃口值 枚举完毕
            j++;
        }
        if (j < n) {	//如果某一个 饼干 和 胃口值 满足条件，则答案加一
            count++;
        }
    }
    return count;
}