1.2 分配問題

455. Assign Cookies

題目描述

有一群孩子和一堆餅乾，每個孩子有一個飢餓度，每個餅乾都有一個飽腹度。每個孩子只能吃一個餅乾，且只有餅乾的飽腹度不小於孩子的飢餓度時，這個孩子才能吃飽。求解最多有多少孩子可以吃飽。

輸入輸出範例

輸入兩個陣列，分別代表孩子的飢餓度和餅乾的飽腹度。輸出可以吃飽的孩子的最大數量。

Input: [1,2], [1,2,3]
Output: 2

在這個範例中，我們可以給兩個孩子餵 [1,2]、[1,3]、[2,3] 這三種組合的任意一種。

題解

因為飢餓度最小的孩子最容易吃飽，所以我們先考慮這個孩子。為了盡量使得剩下的餅乾可以滿足飢餓度更大的孩子，我們應該把大於等於這個孩子飢餓度的、且大小最小的餅乾給這個孩子。滿足了這個孩子之後，我們採取同樣的策略，考慮剩下孩子裡飢餓度最小的孩子，直到沒有滿足條件的餅乾存在。

簡而言之，這裡的貪心策略是，給剩餘孩子裡最小飢餓度的孩子分配最小的能飽腹的餅乾。至於具體實現，因為我們需要獲得大小關係，一個便捷的方法就是把孩子和餅乾分別排序。這樣我們就可以從飢餓度最小的孩子和飽腹度最小的餅乾出發，計算有多少個配對可以滿足條件。

注意

對陣列或字符串排序是常見的操作，方便之後的大小比較。排序順序默認是從小到大。

注意

在之後的講解中，若我們談論的是對連續空間的變量進行操作，我們並不會明確區分陣列和字符串，因為它們本質上都是在連續空間上的有序變量集合。一個字符串 "abc" 可以被看作一個陣列 ['a', 'b', 'c']。

C++

int findContentChildren(vector<int> &children, vector<int> &cookies) {
    sort(children.begin(), children.end());
    sort(cookies.begin(), cookies.end());
    int child_i = 0, cookie_i = 0;
    int n_children = children.size(), n_cookies = cookies.size();
    while (child_i < n_children && cookie_i < n_cookies) {
        if (children[child_i] <= cookies[cookie_i]) {
            ++child_i;
        }
        ++cookie_i;
    }
    return child_i;
}

Python

def findContentChildren(children: List[int], cookies: List[int]) -> int:
    children.sort()
    cookies.sort()
    child_i, cookie_i = 0, 0
    n_children, n_cookies = len(children), len(cookies)
    while child_i < n_children and cookie_i < n_cookies:
        if children[child_i] <= cookies[cookie_i]:
            child_i += 1
        cookie_i += 1
    return child_i

複雜度分析

• 時間複雜度：排序的時間為 $O(n \log n)$，雙指針遍歷的時間為 $O(n)$，因此總時間複雜度為： $$O(n_{\text{children}} \log n_{\text{children}} + n_{\text{cookies}} \log n_{\text{cookies}})$$
• 空間複雜度：排序需要額外的 $O(n)$ 空間，總空間複雜度為： $$O(n_{\text{children}} + n_{\text{cookies}})$$

135. Candy

題目描述

一群孩子站成一排，每一個孩子有自己的評分。現在需要給這些孩子發糖果，規則是如果一個孩子的評分比自己身旁的一個孩子要高，那麼這個孩子就必須得到比身旁孩子更多的糖果。所有孩子至少要有一個糖果。求解最少需要多少個糖果。

輸入輸出範例

輸入是一個陣列，表示孩子的評分。輸出是最少糖果的數量。

Input: [1,0,2]
Output: 5

在這個範例中，最少的糖果分配方式是 [2,1,2]。

題解

存在比較關係的貪心策略並不一定需要排序。雖然這一道題也是運用貪心策略，但我們只需要簡單的兩次遍歷即可：把所有孩子的糖果數初始化為 1；先從左往右遍歷一遍，如果右邊孩子的評分比左邊的高，則右邊孩子的糖果數更新為左邊孩子的糖果數加 1；再從右往左遍歷一遍，如果左邊孩子的評分比右邊的高，且左邊孩子當前的糖果數不大於右邊孩子的糖果數，則左邊孩子的糖果數更新為右邊孩子的糖果數加 1。通過這兩次遍歷，分配的糖果就可以滿足題目要求了。這裡的貪心策略即為，在每次遍歷中，只考慮並更新相鄰一側的大小關係。

在範例中，我們初始化糖果分配為 [1,1,1]，第一次遍歷更新後的結果為 [1,1,2]，第二次遍歷更新後的結果為 [2,1,2]。

C++

int candy(vector<int>& ratings) {
    int n = ratings.size();
    vector<int> candies(n, 1);
    for (int i = 1; i < n; ++i) {
        if (ratings[i] > ratings[i - 1]) {
            candies[i] = candies[i - 1] + 1;
        }
    }
    for (int i = n - 1; i > 0; --i) {
        if (ratings[i] < ratings[i - 1]) {
            candies[i - 1] = max(candies[i - 1], candies[i] + 1);
        }
    }
    return accumulate(candies.begin(), candies.end(), 0);
}

Python

def candy(ratings_list: List[int]) -> int:
    n = len(ratings_list)
    candies = [1] * n
    for i in range(1, n):
        if ratings_list[i] > ratings_list[i - 1]:
            candies[i] = candies[i - 1] + 1
    for i in range(n - 1, 0, -1):
        if ratings_list[i] < ratings_list[i - 1]:
            candies[i - 1] = max(candies[i - 1], candies[i] + 1)
    return sum(candies)

複雜度分析

• 時間複雜度

  • 從左到右遍歷和從右到左遍歷各需花費 $O(n)$ 的時間。
  • 總時間複雜度為 $O(n)$。

• 空間複雜度

  • 使用一個額外的陣列 candies 來儲存每個小孩的糖果數量，因此空間複雜度為 $O(n)$。