題目描述:有 n 個小孩排成一排,每人有一個評分 ratings[i]。需要分配糖果,規則為:每人至少 1 顆;若某小孩的評分嚴格大於相鄰小孩,則必須拿到比那位相鄰小孩更多的糖果。求最少需要準備幾顆糖果。
解題思路:這道題的困難在於每個位置同時受左右兩側影響,若試圖一次性計算很容易顧此失彼。
兩次掃描(Two-Pass Greedy) 是最直觀的 O(n) 解法:
candies,每人先給 1 顆。ratings[i] > ratings[i-1],則 candies[i] = candies[i-1] + 1。此步確保每人比左邊高分的鄰居多一顆。ratings[i] > ratings[i+1],則 candies[i] = max(candies[i], candies[i+1] + 1)。此步確保每人比右邊高分的鄰居多一顆,同時用 max 保留已滿足的左側約束。candies 求總和即為答案。取 max 是關鍵:若位置 i 同時比左右都高,左右兩次掃描都會對其加分,取兩者最大值才能同時滿足兩側約束。
時間複雜度:O(n) — 對陣列進行兩次線性掃描,每次 O(n),最後求和也是 O(n),整體為 O(n)。
空間複雜度:O(n) — 需要額外的 candies 陣列來儲存每位小孩分配到的糖果數量。若使用下方的單次掃描 O(1) 空間解法則可降至 O(1)。
1. Initialize candies[i] = 1 for all i. 2. Left-to-right pass (i from 1 to n-1): a. If ratings[i] > ratings[i-1], set candies[i] = candies[i-1] + 1. 3. Right-to-left pass (i from n-2 down to 0): a. If ratings[i] > ratings[i+1], set candies[i] = max(candies[i], candies[i+1] + 1). 4. Return sum of candies array.
方法一:單次掃描 + 數學計算(O(1) 空間)
觀察評分序列中的遞增段(上坡)與遞減段(下坡)。對於連續遞增段長度 up 和遞減段長度 down,可用等差數列公式直接計算糖果總數,避免額外陣列。峰值(局部最大值)的糖果數為 max(up, down) + 1。時間複雜度 O(n),空間複雜度 O(1)。實作較複雜,需要仔細處理邊界與峰值歸屬。
方法二:兩次掃描(本題主解法) 如上所述,先從左到右保證每人比評分更低的左鄰多一顆糖,再從右到左保證每人比評分更低的右鄰多一顆糖,取兩次結果的最大值。時間複雜度 O(n),空間複雜度 O(n)。邏輯最清晰,是面試時最推薦的解法。
方法三:暴力迭代 反覆掃描陣列,每次發現違反約束的位置就調整,直到沒有違反為止。最壞情況需要 O(n) 輪,每輪 O(n),總時間 O(n²),效率低,不推薦。