? ? ? ? ?在算法面試中，“分發糖果” 是一道經典的貪心算法應用題，核心考察對 “局部最優推導全局最優” 的理解。本文將從問題分析出發，提供兩種主流解題思路，并附上 C++ 實現代碼，幫助你徹底掌握這道題。

一、問題重述

題目要求

有?n?個孩子站成一排，每個孩子有評分?ratings[i]，分發糖果需滿足：

1. 每個孩子至少得 1 顆糖果；
2. 相鄰孩子中，評分高的孩子必須獲得更多糖果。
   求最少需要準備的糖果總數。

示例理解

• 示例 1：ratings = [1,0,2]
  分發方案?[2,1,2]，總數?5。
  解釋：第二個孩子評分最低（0）得 1 顆，第一個比第二個高（1>0）得 2 顆，第三個比第二個高（2>0）得 2 顆。
• 示例 2：ratings = [1,2,2]
  分發方案?[1,2,1]，總數?4。
  解釋：第三個孩子與第二個評分相同（2=2），無需更多糖果，故得 1 顆（滿足 “至少 1 顆” 即可）。

二、解題思路

核心難點

相鄰關系是 “雙向約束”：既要保證 “左→右” 方向評分高的糖果多，也要保證 “右→左” 方向評分高的糖果多。若只單向處理，會導致另一側約束被破壞。

思路 1：兩次遍歷（貪心經典解法）

原理

貪心算法的核心是 “分階段滿足約束”：

1. 左→右遍歷：保證每個孩子比左邊評分高時，糖果數比左邊多（不考慮右邊）；
2. 右→左遍歷：保證每個孩子比右邊評分高時，糖果數比右邊多（此時需結合左→右的結果，取最大值，避免破壞左側約束）。

步驟拆解

1. 初始化數組?candies，所有元素為 1（滿足 “至少 1 顆”）；
2. 左→右遍歷（處理 “左邊約束”）：
   若?ratings[i] > ratings[i-1]，則?candies[i] = candies[i-1] + 1；
3. 右→左遍歷（處理 “右邊約束”）：
   若?ratings[i] > ratings[i+1]，則?candies[i] = max(candies[i], candies[i+1] + 1)；
4. 求和?candies?數組，得到最少糖果總數。

示例驗證（以?ratings = [1,0,2]?為例）

• 初始化：candies = [1,1,1]
• 左→右遍歷：
  i=1（0 <1）：無變化；i=2（2> 0）：candies[2] = 1+1=2?→ 此時?[1,1,2]
• 右→左遍歷：
  i=1（0 <2）：無變化；i=0（1> 0）：candies[0] = max(1, 1+1)=2?→ 最終?[2,1,2]
• 求和：2+1+2=5（正確）

思路 2：一次遍歷（優化空間，進階解法）

原理

觀察到 “糖果數的變化與評分的遞增 / 遞減序列相關”，可通過記錄當前遞增 / 遞減序列的長度，動態計算糖果數，無需額外存儲?candies?數組（空間復雜度從 O (n) 降至 O (1)）。

關鍵概念

• up：當前遞增序列的長度（評分持續上升時，每多一個孩子，糖果數 + 1）；
• down：當前遞減序列的長度（評分持續下降時，每多一個孩子，糖果數需回溯調整，避免重復計算）；
• pre：前一個孩子的糖果數（動態更新）。

步驟拆解

1. 初始化?result=1（第一個孩子至少 1 顆）、up=1、down=0、pre=1；
2. 從第二個孩子開始遍歷：
   • 若?ratings[i] > ratings[i-1]（遞增）：
     up = pre + 1，down=0，pre=up，result += up；
   • 若?ratings[i] == ratings[i-1]（相等）：
     up=1，down=0，pre=1，result += 1（相等時無需更多糖果，取 1 即可）；
   • 若?ratings[i] < ratings[i-1]（遞減）：
     down += 1，up=1，
     若?down == pre（遞減序列長度等于前一個糖果數，需補 1 避免沖突）：result += 1，
     result += down，pre=1（遞減序列中當前孩子糖果數為 1，前一個需回溯調整）；
3. 遍歷結束，result?即為最少糖果總數。

示例驗證（以?ratings = [1,2,2]?為例）

• 初始：result=1，up=1，down=0，pre=1
• i=1（2>1，遞增）：
  up=2，pre=2，result=1+2=3
• i=2（2=2，相等）：
  pre=1，result=3+1=4（正確）

三、C++ 代碼實現

實現 1：兩次遍歷（易理解，推薦面試首選）

#include <iostream>
#include <vector>
#include <algorithm> // for max()using namespace std;class Solution {
public:int candy(vector<int>& ratings) {int n = ratings.size();if (n == 0) return 0;// 初始化：每個孩子至少1顆糖果vector<int> candies(n, 1);// 左→右遍歷：處理左邊約束（比左邊高則+1）for (int i = 1; i < n; ++i) {if (ratings[i] > ratings[i-1]) {candies[i] = candies[i-1] + 1;}}// 右→左遍歷：處理右邊約束（比右邊高則取max(當前, 右邊+1)）for (int i = n-2; i >= 0; --i) {if (ratings[i] > ratings[i+1]) {candies[i] = max(candies[i], candies[i+1] + 1);}}// 求和int total = 0;for (int num : candies) {total += num;}return total;}
};// 測試代碼
int main() {Solution sol;vector<int> ratings1 = {1,0,2};cout << "示例1最少糖果數：" << sol.candy(ratings1) << endl; // 輸出5vector<int> ratings2 = {1,2,2};cout << "示例2最少糖果數：" << sol.candy(ratings2) << endl; // 輸出4return 0;
}

實現 2：一次遍歷（空間優化，進階）

#include <iostream>
#include <vector>using namespace std;class Solution {
public:int candy(vector<int>& ratings) {int n = ratings.size();if (n == 0) return 0;if (n == 1) return 1;int result = 1;  // 第一個孩子的1顆糖果int up = 1;      // 當前遞增序列長度int down = 0;    // 當前遞減序列長度int pre = 1;     // 前一個孩子的糖果數for (int i = 1; i < n; ++i) {if (ratings[i] > ratings[i-1]) {// 遞增序列up = pre + 1;down = 0;pre = up;result += up;} else if (ratings[i] == ratings[i-1]) {// 相等：當前孩子取1顆，重置狀態up = 1;down = 0;pre = 1;result += 1;} else {// 遞減序列down += 1;up = 1;// 若遞減長度等于前一個糖果數，需補1（避免沖突）if (down == pre) {down += 1;}result += down;pre = 1;  // 遞減序列中當前孩子糖果數為1}}return result;}
};// 測試代碼
int main() {Solution sol;vector<int> ratings1 = {1,0,2};cout << "示例1最少糖果數：" << sol.candy(ratings1) << endl; // 輸出5vector<int> ratings2 = {1,2,2};cout << "示例2最少糖果數：" << sol.candy(ratings2) << endl; // 輸出4return 0;
}

四、復雜度分析

五、總結

1. 兩次遍歷解法的核心是 “分階段滿足雙向約束”，通過兩次單向遍歷覆蓋所有相鄰關系，邏輯清晰，適合面試中快速實現；
2. 一次遍歷解法通過動態記錄序列長度優化空間，需要對 “遞減序列的回溯調整” 有深入理解，適合進階學習；
3. 無論哪種解法，都遵循貪心算法的 “局部最優→全局最優” 思想：每次只處理當前能確定的最優解，最終累積得到全局最少糖果數。

建議先掌握兩次遍歷解法，再嘗試理解一次遍歷的優化邏輯，逐步提升對貪心算法的應用能力。