⭐️小剧场⭐️

你去到一个幼儿园里做活动，一群小朋友围着你转，你发现你的口袋里有一些大小不一的饼干，你想分给孩子们。对每个孩子，都有一个胃口值 ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干，都有一个尺寸  。如果 ，我们可以将这个饼干 分配给孩子 ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。（一定要认真将自己代入成这个家长，你会怎样去分？）答案及解析在下

题目连接：分发饼干https://leetcode-cn.com/problems/assign-cookies/

🍋1.什么是贪心算法？

       贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

       说这么多，用题目来演示学习才是最快的，我将由简到难，一步步带大家做一个够贪的刷题者

🍋2.贪心的经典基础例题

 PS：建议先读完题目通过链接思考后看能否想到如何贪心，没有头绪再看下方的贪心考虑，理解后再自己去尝试用代码实现。

🍈1.两个数对之间的最大乘积差（易）

 两个数对 (a, b) 和 (c, d) 之间的 乘积差 定义为 (a * b) - (c * d) 。

例如，(5, 6) 和 (2, 7) 之间的乘积差是 (5 * 6) - (2 * 7) = 16 。

给你一个整数数组 nums ，选出四个 不同的 下标 w、x、y 和 z ，使数对 (nums[w], nums[x]) 和 (nums[y], nums[z]) 之间的 乘积差 取到 最大值 。

返回以这种方式取得的乘积差中的 最大值 。

题目连接：两个数对之间的最大乘积差https://leetcode-cn.com/problems/maximum-product-difference-between-two-pairs/        

代码展示：

class Solution {
    public int maxProductDifference(int[] nums) {
        Arrays.sort(nums);
        int n=nums.length;
        return nums[n-1]*nums[n-2]-nums[0]*nums[1];//最大的相乘减去最小的相乘
    }
}

       🌰贪心考虑：要获得一个最大的差值，那我们肯定想着需要用一个最大的值减去一个最小的值。那如何从获得一个乘积最大和一个乘积最小的值呢？那肯定是最大的数乘第二大的数的和最小的数乘以第二小的数。所以我们直接排序后，用最大的两个数相乘减去最小的两个数相乘就是答案啦。                                

🍈2.三角形的最大周长(易）

给定由一些正数（代表长度）组成的数组 A，返回由其中三个长度组成的、面积不为零的三角形的最大周长。

如果不能形成任何面积不为零的三角形，返回 0。

题目链接：三角形的最大周长https://leetcode-cn.com/problems/largest-perimeter-triangle/

代码展示：

class Solution {
    public int largestPerimeter(int[] nums) {
        Arrays.sort(nums);   //先排序
        int n=nums.length;
        for(int i=n-1;i>=2;i--){    //倒叙遍历（从最大的开始判断）
            int x=nums[i-1]+nums[i-2];    //判断后两条边是否能满足围成三角形
            if(x>nums[i]){
                return x+nums[i];
            }
        }
        return 0;
    }
}

       🌰贪心考虑：又是一道题目中包含最大字眼的例题。先思考如何让三角形周长最大？那肯定三条边越长越好呀。我们可以直接将三条边捆绑着来看，比如有一个排序好的数组[1,2,2,3,4,7]，你肯定先判断3,4,7能否围成三角形，发现不能，那你觉得7这条边还能用上吗？肯定不能了，因为除了7最长的3和4加起来都构不成三角形，其他更加不可能。所以我再考虑2,3,4三条边，这次发现可以了，所以2,3,4就是能围成最大三角形的三条边。  

🍈3.数组拆分|（易）

给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。

返回该 最大总和 。

题目链接：数组拆分| https://leetcode-cn.com/problems/array-partition-i/

代码展示：

class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);  //同样先将数组从小到大排序
        int n=nums.length;
        int count=0;
        for(int i=0;i<n;i+=2){    //只取偶数位相加即为答案
            count+=nums[i];
        }
        return count;
    }
}

       🌰贪心考虑：题目要求将数组两两配对，每一对只取更小的那个数，另外一个将会被浪费掉。假设有个排好序的数组(a1,a2,a3.....an)，a1作为最小的数，那么和它匹配的数，肯定要被浪费掉，那我们肯定希望被浪费的数越小越好，那除了a1最小的就是a2了呀，所以a1和a2匹配。这样同理又从a3开始匹配，a3把a4带走浪费掉，所以最后我们取得的数下标都是从0开始的偶数位，所以将索引为偶数位相加就是最大的值了。  

🍈4.救生艇（中）

第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。

每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。

返回载到每一个人所需的最小船数。(保证每个人都能被船载)。

题目链接：救生艇 https://leetcode-cn.com/problems/boats-to-save-people/ 

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        int ans = 0;
        Arrays.sort(people);//让人从轻到重排好序站好
        int light = 0;
        int heavy = people.length - 1;//利用双指针
        while (light <= heavy) {
            if (people[light] + people[heavy] <= limit) {//判断此时最轻的和最重的能否坐一起
                ++light;    //可以的话左指针右移（说明最轻的跟着最重的一起走了）
            }
            --heavy;   //右指针左移，无论能不能带一个最轻的，这个重的都得走
            ++ans;
        }
        return ans;
    }
}

       🌰贪心考虑：首先我们要明白，人肯定是全都要带走的，它也不可能有一个人的体重直接超过船的承受重量的，这样的话题目就出错了。为了减少船的次数，我们无非只能希望在带最重的人的同时再带走一个人，带谁呢？那最有可能的当然是场上最轻的人，如果这个最重的人和最轻的人加一起都超重，那这个最重的人自己注定只能自己走了。然后再继续重复判断剩下里面的人最重的能否和最轻的走，直到所有人走完。所以我们可以通过双指针来分别指向场上最轻的和最重的来进行选人。  

🍈5.分发饼干（小剧场解答）

       🌰贪心考虑：同样是求最值问题，这道理和上一题有异曲同工之妙。我们的目标是为了满足更多的孩子，那当然是优先满足容易吃饱的孩子，所以我们需要将孩子排好序。对于饼干呢？我们当然更想先把尺寸较小的饼干给孩子们吃掉，而不是一上来就把大饼干拿出来，所以我们同样要给饼干也排序。综合两种贪心的思想：我们就想要尽可能用尺寸最小的饼干去喂饱最容易吃饱的孩子。既然如此就会出现两种情况：1.最小的饼干能喂饱最容易吃饱的孩子，这种情况我们是我们希望见到的。2.最小的饼干满足不了最容易吃饱的孩子，那你这块饼干说明就没用了，你连最容易喂饱的都喂不饱，那还有什么用，那只能考虑尺寸更大一定的饼干。综上考虑，我们同样得用双指针，分别指向此时最容易吃饱的孩子和尺寸最小的饼干。                      

 代码展示：

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int n1=g.length;//孩子的个数
        int n2=s.length;//饼干的个数
        int l=0;//指向最容易吃饱的孩子的指针
        int r=0;//指向尺寸最小的饼干的指针
        int count=0;
        while(l<n1&&r<n2){ //如果孩子喂完了或者饼干吃完都会结束
            if(s[r]>=g[l]){    //如果最小的饼干能满足最容易吃饱的孩子
                r++;        //孩子指针右移
                l++;        //饼干指针右移
                count++;    
            }else{    //如果满足不了最小的孩子
                r++;  //舍弃当前饼干，饼干指针右移再次继续判断
            }
        }
        return count;
    }
}

🍈6. 最少操作使数组递增（易）

给你一个整数数组 nums （下标从 0 开始）。每一次操作中，你可以选择数组中一个元素，并将它增加 1 。

比方说，如果 nums = [1,2,3] ，你可以选择增加 nums[1] 得到 nums = [1,3,3] 。

请你返回使 nums 严格递增 的 最少 操作次数。

我们称数组 nums 是 严格递增的 ，当它满足对于所有的 0 <= i < nums.length - 1 都有 nums[i] < nums[i+1] 。一个长度为 1 的数组是严格递增的一种特殊情况。

题目链接：最少操作使数组递增https://leetcode-cn.com/problems/minimum-operations-to-make-the-array-increasing/

代码展示：

class Solution {
    public int minOperations(int[] nums) {
        int n=nums.length;
        if(n==1) return 0;
        int count=0;   //用于统计操作的次数
        for(int i=1;i<n;i++){    //从下标为1的位置开始判断
            int x=nums[i-1]-nums[i];    //计算差值
            if(x>=0){    
                count=count+x+1;    //加上操作的次数
                nums[i]=nums[i-1]+1;    
            }
        }
        return count;
    }
}

       🌰贪心考虑：既然要严格递增，又要最少次数。因为我们是通过变大使数组递增，所以我们得从左向右判断，会出现两种情况：1.当nums[i]比nums[i-1]大时，这时已经递增，不需要操作。2.当nums[i]比nums[i-1]小时，为了形成严格递增，用时为了减少操作次数，我们应该nums[i]变得正好比nums[i-1]大1即可。此时操作的次数就是nums[i-1]-nums[i]+1。遍历完数组后将每次的操作次数加起来即可。        

🍋3.贪心思想适用于哪些题目？

       如果仔细的兄弟肯定发现上面的例题都包含着最少，最多，尽可能等字眼，这确实是可以尝试用贪心思想的重要标志之一 。一般适用于最优化等问题，当然我这例举的题目都是非常简单和基础的，能帮助兄弟们快速感受贪心思想的题目。贪心之所以难，是因为你根本想不到如何去贪，它没有固定模板，所以需要大家从最开始刷题就尝试去练习这种思想