# 0455. 分發餅干 ## 題目地址(455. 分發餅干) <https://leetcode-cn.com/problems/assign-cookies/> ## 題目描述 ``` <pre class="calibre18">``` 假設你是一位很棒的家長，想要給你的孩子們一些小餅干。但是，每個孩子最多只能給一塊餅干。對每個孩子 i ，都有一個胃口值 gi ，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干 j ，都有一個尺寸 sj 。如果 sj >= gi ，我們可以將這個餅干 j 分配給孩子 i ，這個孩子會得到滿足。你的目標是盡可能滿足越多數量的孩子，并輸出這個最大數值。 注意： 你可以假設胃口值為正。 一個小朋友最多只能擁有一塊餅干。 示例 1: 輸入: [1,2,3], [1,1] 輸出: 1 解釋: 你有三個孩子和兩塊小餅干，3個孩子的胃口值分別是：1,2,3。 雖然你有兩塊小餅干，由于他們的尺寸都是1，你只能讓胃口值是1的孩子滿足。 所以你應該輸出1。 示例 2: 輸入: [1,2], [1,2,3] 輸出: 2 解釋: 你有兩個孩子和三塊小餅干，2個孩子的胃口值分別是1,2。 你擁有的餅干數量和尺寸都足以讓所有孩子滿足。 所以你應該輸出2. ``` ``` ## 前置知識 - [貪心算法](https://github.com/azl397985856/leetcode/blob/master/thinkings/greedy.md) - 雙指針 ## 公司 - 阿里 - 騰訊 - 字節 ## 思路 貪心算法+雙指針求解 給一個孩子的餅干應當盡量小并且能滿足孩子，大的留來滿足胃口大的孩子。因為胃口小的孩子最容易得到滿足，所以優先滿足胃口小的孩子需求。按照從小到大的順序使用餅干嘗試是否可滿足某個孩子。 ## 關鍵點 將需求因子 g 和 s 分別從小到大進行排序，使用貪心思想，配合雙指針，每個餅干只嘗試一次，成功則換下一個孩子來嘗試。 ## 代碼 - 語言支持：JS ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {number[]} g * @param {number[]} s * @return {number} */</span> <span class="hljs-keyword">const</span> findContentChildren = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">g, s</span>) </span>{ g = g.sort((a, b) => a - b); s = s.sort((a, b) => a - b); <span class="hljs-keyword">let</span> gi = <span class="hljs-params">0</span>; <span class="hljs-title">// 胃口值</span> <span class="hljs-keyword">let</span> sj = <span class="hljs-params">0</span>; <span class="hljs-title">// 餅干尺寸</span> <span class="hljs-keyword">let</span> res = <span class="hljs-params">0</span>; <span class="hljs-keyword">while</span> (gi < g.length && sj < s.length) { <span class="hljs-title">// 當餅干 sj >= 胃口 gi 時，餅干滿足胃口，更新滿足的孩子數并移動指針</span> <span class="hljs-keyword">if</span> (s[sj] >= g[gi]) { gi++; sj++; res++; } <span class="hljs-keyword">else</span> { <span class="hljs-title">// 當餅干 sj < 胃口 gi 時，餅干不能滿足胃口，需要換大的</span> sj++; } } <span class="hljs-keyword">return</span> res; }; ``` ``` ***復雜度分析*** - 時間復雜度：由于使用了排序，因此時間復雜度為 O(NlogN) - 空間復雜度：O(1) 更多題解可以訪問我的LeetCode題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經37K star啦。 關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。