貪心的第一道題目，快看看你夠不夠貪心

455.分發(fā)餅干

力扣題目鏈接：https://leetcode-cn.com/problems/assign-cookies

假設(shè)你是一位很棒的家長(zhǎng)，想要給你的孩子們一些小餅干。但是，每個(gè)孩子最多只能給一塊餅干。

對(duì)每個(gè)孩子 i，都有一個(gè)胃口值 g[i]，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干 j，都有一個(gè)尺寸 s[j]。如果 s[j]>= g[i]，我們可以將這個(gè)餅干 j 分配給孩子 i ，這個(gè)孩子會(huì)得到滿足。你的目標(biāo)是盡可能滿足越多數(shù)量的孩子，并輸出這個(gè)最大數(shù)值。

示例1:

• 輸入: g = [1,2,3], s = [1,1]
• 輸出: 1 解釋:你有三個(gè)孩子和兩塊小餅干，3個(gè)孩子的胃口值分別是：1,2,3。雖然你有兩塊小餅干，由于他們的尺寸都是1，你只能讓胃口值是1的孩子滿足。所以你應(yīng)該輸出1。

示例2:

• 輸入: g = [1,2], s = [1,2,3]
• 輸出: 2
• 解釋:你有兩個(gè)孩子和三塊小餅干，2個(gè)孩子的胃口值分別是1,2。你擁有的餅干數(shù)量和尺寸都足以讓所有孩子滿足。所以你應(yīng)該輸出2.

提示：

• 1 <= g.length <= 3 * 10^4
• 0 <= s.length <= 3 * 10^4
• 1 <= g[i], s[j] <=?2^31 - 1

思路

為了了滿足更多的小孩，就不要造成餅干尺寸的浪費(fèi)。

大尺寸的餅干既可以滿足胃口大的孩子也可以滿足胃口小的孩子，那么就應(yīng)該優(yōu)先滿足胃口大的。

這里的局部最優(yōu)就是大餅干喂給胃口大的，充分利用餅干尺寸喂飽一個(gè)，全局最優(yōu)就是喂飽盡可能多的小孩。

可以嘗試使用貪心策略，先將餅干數(shù)組和小孩數(shù)組排序。

然后從后向前遍歷小孩數(shù)組，用大餅干優(yōu)先滿足胃口大的，并統(tǒng)計(jì)滿足小孩數(shù)量。

如圖：

這個(gè)例子可以看出餅干9只有喂給胃口為7的小孩，這樣才是整體最優(yōu)解，并想不出反例，那么就可以擼代碼了。

C++代碼整體如下：

//時(shí)間復(fù)雜度：O(nlogn)
//空間復(fù)雜度：O(1)
classSolution{
public:
intfindContentChildren(vector<int>&g,vector<int>&s){
sort(g.begin(),g.end());
sort(s.begin(),s.end());
intindex=s.size()-1;//餅干數(shù)組的下表
intresult=0;
for(inti=g.size()-1;i>=0;i--){
if(index>=0&&s[index]>=g[i]){
result++;
index--;
}
}
returnresult;
}
};

從代碼中可以看出我用了一個(gè)index來(lái)控制餅干數(shù)組的遍歷，遍歷餅干并沒(méi)有再起一個(gè)for循環(huán)，而是采用自減的方式，這也是常用的技巧。

有的同學(xué)看到要遍歷兩個(gè)數(shù)組，就想到用兩個(gè)for循環(huán)，那樣邏輯其實(shí)就復(fù)雜了。

也可以換一個(gè)思路，小餅干先喂飽小胃口

代碼如下：

classSolution{
public:
intfindContentChildren(vector<int>&g,vector<int>&s){
sort(g.begin(),g.end());
sort(s.begin(),s.end());
intindex=0;
for(inti=0;iif(indexreturnindex;
}
};

總結(jié)

這道題是貪心很好的一道入門(mén)題目，思路還是比較容易想到的。

文中詳細(xì)介紹了思考的過(guò)程，想清楚局部最優(yōu)，想清楚全局最優(yōu)，感覺(jué)局部最優(yōu)是可以推出全局最優(yōu)，并想不出反例，那么就試一試貪心。

其他語(yǔ)言版本

Java

classSolution{
//思路1：優(yōu)先考慮餅干，小餅干先喂飽小胃口
publicintfindContentChildren(int[]g,int[]s){
Arrays.sort(g);
Arrays.sort(s);
intstart=0;
intcount=0;
for(inti=0;iif(s[i]>=g[start]){
start++;
count++;
}
}
returncount;
}
}

classSolution{
//思路2：優(yōu)先考慮胃口，先喂飽大胃口
publicintfindContentChildren(int[]g,int[]s){
Arrays.sort(g);
Arrays.sort(s);
intcount=0;
intstart=s.length-1;
//遍歷胃口
for(intindex=g.length-1;index>=0;index--){
if(start>=0&&g[index]<=?s[start])?{
????????????????start--;
????????????????count++;
????????????}
????????}
????????returncount;
}
}

Python

class Solution:
    # 思路1：優(yōu)先考慮胃餅干
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        res = 0
        for i in range(len(s)):
            if res = g[res]:  #小餅干先喂飽小胃口
                res += 1
        return res

classSolution:
#思路2：優(yōu)先考慮胃口
deffindContentChildren(self,g:List[int],s:List[int])->int:
g.sort()
s.sort()
start,count=len(s)-1,0
forindexinrange(len(g)-1,-1,-1):#先喂飽大胃口
ifstart>=0andg[index]<=?s[start]:
????????????????start?-=?1
count+=1
returncount

Go

//排序后，局部最優(yōu)
funcfindContentChildren(g[]int,s[]int)int{
sort.Ints(g)
sort.Ints(s)

//從小到大
child:=0
forsIdx:=0;childlen(g)&&sIdxlen(s);sIdx++{
ifs[sIdx]>=g[child]{//如果餅干的大小大于或等于孩子的為空則給與，否則不給予，繼續(xù)尋找選一個(gè)餅干是否符合
child++
}
}

returnchild
}

審核編輯 ：李倩