[[434135]]

分發(fā)餅干

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

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

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

示例 1:

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

示例 2:

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

提示：

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

思路

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

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

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

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

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

如圖：

分發(fā)餅干

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

C++代碼整體如下：

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

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

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

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

代碼如下：

class Solution { 
public: 
    int findContentChildren(vector<int>& g, vector<int>& s) { 
        sort(g.begin(),g.end()); 
        sort(s.begin(),s.end()); 
        int index = 0; 
        for(int i = 0;i < s.size();++i){ 
            if(index < g.size() && g[index] <= s[i]){ 
                index++; 
            } 
        } 
        return index; 
    } 
}; 

總結(jié)

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

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

本文轉(zhuǎn)載自微信公眾號(hào)「代碼隨想錄」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系代碼隨想錄公眾號(hào)。