題目描述:有 g 個孩子和 s 塊餅乾。g[i] 表示第 i 個孩子的最低胃口值,s[j] 表示第 j 塊餅乾的大小。每個孩子最多只能獲得一塊餅乾,且只有當 s[j] >= g[i] 時,第 j 塊餅乾才能滿足第 i 個孩子。求最多能滿足幾個孩子。
解題思路:
貪心策略:用最大的餅乾去滿足胃口最大的孩子。
直覺:最大的餅乾能且只能滿足一個孩子。若要最大化滿足的孩子數,應該把它分給「能被它滿足的孩子中,胃口最大的那個」。這樣更小的餅乾就能留給胃口更小的孩子,不浪費。
演算法步驟:
g(胃口)和 s(餅乾)都從小到大排序i 指向孩子,j 指向餅乾,兩者均從最大值開始往左掃s[j] >= g[i]:當前最大餅乾可以滿足當前最大胃口的孩子,計數 +1,兩個指針都左移s[j] < g[i]:當前最大餅乾連最大胃口都滿足不了,這塊餅乾對所有孩子都沒用,j 左移捨棄等價的從小到大做法:也可以從最小的孩子和最小的餅乾開始,盡量用最小能滿足的餅乾滿足每個孩子,結果相同。
時間複雜度:O(m log m + n log n) — 排序兩個陣列的時間,其中 m = g.size(),n = s.size()。雙指針掃描為 O(m + n),瓶頸在排序。
空間複雜度:O(1) 或 O(log n) — 若計入排序的遞迴棧空間為 O(log n),否則額外空間為 O(1)(只使用了 i、j、satisfied 三個變數)。
函數 findContentChildren(g, s):
步驟 1:排序
將 g 升序排序
將 s 升序排序
步驟 2:雙指針,從最大值往左掃
satisfied = 0
i = g 的最後一個索引(最大胃口孩子)
j = s 的最後一個索引(最大餅乾)
當 i >= 0 且 j >= 0 時:
若 s[j] >= g[i]:
此餅乾能滿足此孩子
satisfied = satisfied + 1
i = i - 1
j = j - 1
否則:
此餅乾太小,捨棄
j = j - 1
步驟 3:回傳
回傳 satisfied排序後從最小的孩子和最小的餅乾開始,用最小能滿足當前孩子的餅乾滿足他:
int i = 0, j = 0;
while (i < g.size() && j < s.size()) {
if (s[j] >= g[i]) ++i; // 滿足孩子 i,移向下一個孩子
++j; // 無論是否滿足,這塊餅乾已用完或放棄
}
return i; // i 即滿足的孩子數
邏輯更簡潔:每塊餅乾只嘗試滿足當前最小未滿足的孩子,若夠就移向下一個孩子。兩種方向均正確,時間複雜度相同。
對排序後的 s,對每個孩子的胃口 g[i] 用 lower_bound 找到最小能滿足的餅乾,並將其「標記為已使用」。
時間 O(m log n)(m 個孩子,每次二分 O(log n)),但實作需要額外標記陣列或刪除操作,反而比雙指針複雜。在 m << n 時有優勢。
將所有餅乾放入 multiset<int>,對每個孩子(胃口升序),用 lower_bound(g[i]) 找最小可用餅乾並刪除。這和方法二邏輯相同,但利用資料結構實現動態刪除,適合需要動態增刪餅乾的變形題。
一個孩子可以拿多塊餅乾:若放寬限制,每個孩子可以獲得任意多塊餅乾(累積大小 ≥ 胃口即算滿足),如何最大化滿足的孩子數?這成為一個裝箱問題的變形,貪心策略需要重新設計。
最大化總滿意度:若每個孩子被滿足時有不同的「幸福值」,求最大化總幸福值(而非最大化人數),問題如何變化?若幸福值與身高無關,此為一般指派問題,需用匈牙利演算法或 KM 演算法。
贈送策略反轉:若要求最少用幾塊餅乾滿足所有孩子(所有孩子都必須被滿足),問題是否有解?當且僅當每個孩子都有對應的足夠大的餅乾時,可用貪心求最少匹配數;否則無解。這是雙邊匹配問題的特例。