?n 個孩子站成一排。給你一個整數數組 ratings 表示每個孩子的評分。 你需要按照以下要求，給這些孩子分發糖果： 每個孩子至少分配到 1 個糖果。 相鄰兩個孩子評分更高的孩子會獲得更多的糖果。 請你給每個孩子分發糖果，計算并返回需要準備的 最少糖果數目 。
方法一：貪心算法
function candy(ratings: number[]): number {const n = ratings.length;const candies = new Array(n).fill(1);// 從左到右遍歷，保證右邊評分高的孩子糖果多for (let i = 1; i < n; i++) {if (ratings[i] > ratings[i - 1]) {candies[i] = candies[i - 1] + 1;}}// 從右到左遍歷，保證左邊評分高的孩子糖果多for (let i = n - 2; i >= 0; i--) {if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {candies[i] = candies[i + 1] + 1;}}// 計算糖果總數let total = 0;for (const candy of candies) {total += candy;}return total;
}// 示例調用
const ratings = [1, 0, 2];
const result = candy(ratings);
console.log("需要準備的最少糖果數目:", result);
代碼解釋
- 初始化糖果數組：創建一個長度為?
n?的數組?candies，并將每個元素初始化為?1，表示每個孩子至少分配到?1?個糖果。 - 從左到右遍歷：通過?
for?循環從索引?1?到?n - 1?遍歷數組。如果當前孩子的評分?ratings[i]?大于左邊孩子的評分?ratings[i - 1]，則將當前孩子的糖果數?candies[i]?設置為左邊孩子糖果數?candies[i - 1]?加?1，以滿足相鄰孩子評分更高的孩子獲得更多糖果的條件。 - 從右到左遍歷：再通過?
for?循環從索引?n - 2?到?0?反向遍歷數組。如果當前孩子的評分?ratings[i]?大于右邊孩子的評分?ratings[i + 1]，并且當前孩子的糖果數?candies[i]?小于等于右邊孩子的糖果數?candies[i + 1]，則將當前孩子的糖果數?candies[i]?設置為右邊孩子糖果數?candies[i + 1]?加?1，進一步保證滿足條件。 - 計算糖果總數：遍歷?
candies?數組，將每個孩子的糖果數累加到變量?total?中，最后返回?total，即需要準備的最少糖果數目。
復雜度分析
- 時間復雜度：(O(n))，其中?
n?是孩子的數量。代碼中進行了兩次遍歷數組的操作，每次遍歷的時間復雜度都是?(O(n))，最后計算糖果總數的遍歷時間復雜度也為?(O(n))，所以總的時間復雜度為?(O(n))。 - 空間復雜度：(O(n))，用于存儲每個孩子分配的糖果數的數組?
candies?的長度為?n，因此空間復雜度為?(O(n))。
這種貪心算法的思路通過兩次遍歷，分別從不同方向保證了糖果分配滿足條件，從而高效地計算出了最少糖果數目。
方法二：山峰山谷想象法
思路分析
可以將孩子的評分序列看作是一系列的山峰和山谷。對于上升序列（評分遞增），糖果數依次遞增；對于下降序列（評分遞減），糖果數也依次遞減；而在山谷處（評分局部最小），糖果數為 1。我們可以通過一次遍歷找出所有的上升和下降序列，然后計算每個序列所需的糖果數。
代碼實現
function candy(ratings: number[]): number {const n = ratings.length;if (n <= 1) {return n;}let totalCandies = 0;let up = 0; // 上升序列的長度let down = 0; // 下降序列的長度let oldSlope = 0;for (let i = 1; i < n; i++) {// 當前的斜率，1 表示上升， -1 表示下降， 0 表示相等let newSlope = ratings[i] > ratings[i - 1]? 1 : (ratings[i] < ratings[i - 1]? -1 : 0);if ((oldSlope > 0 && newSlope === 0) || (oldSlope < 0 && newSlope >= 0)) {// 當上升序列結束或者下降序列結束時totalCandies += count(up) + count(down) + Math.max(up, down);up = 0;down = 0;}if (newSlope > 0) {up++;} else if (newSlope < 0) {down++;} else {totalCandies++;}oldSlope = newSlope;}// 處理最后一個上升或下降序列totalCandies += count(up) + count(down) + Math.max(up, down) + 1;return totalCandies;
}// 計算長度為 length 的序列所需的糖果數
function count(length: number): number {return (length * (length + 1)) / 2;
}
代碼解釋
-
初始化變量：
n?為孩子的數量。totalCandies?用于記錄總共需要的糖果數，初始化為 0。up?記錄當前上升序列的長度，down?記錄當前下降序列的長度，初始都為 0。oldSlope?記錄上一個位置的斜率，初始為 0。
-
遍歷評分序列：
- 計算當前位置的斜率?
newSlope，如果當前評分大于前一個評分，newSlope?為 1；如果小于，為 -1；如果相等，為 0。 - 當上升序列結束（
oldSlope > 0 && newSlope === 0）或者下降序列結束（oldSlope < 0 && newSlope >= 0）時，計算該上升和下降序列所需的糖果數，并累加到?totalCandies?中，同時重置?up?和?down?為 0。 - 根據?
newSlope?的值更新?up、down?或?totalCandies。如果?newSlope?為 1，up?加 1；如果為 -1，down?加 1；如果為 0，totalCandies?加 1。 - 更新?
oldSlope?為?newSlope。
- 計算當前位置的斜率?
-
處理最后一個序列：
- 遍歷結束后，處理最后一個上升或下降序列，將其所需的糖果數累加到?
totalCandies?中。
- 遍歷結束后，處理最后一個上升或下降序列，將其所需的糖果數累加到?
-
計算序列所需糖果數：
count?函數用于計算長度為?length?的序列所需的糖果數，根據等差數列求和公式?(length * (length + 1)) / 2?計算。
復雜度分析
- 時間復雜度：(O(n))，其中?
n?是孩子的數量。只需要對評分序列進行一次遍歷。 - 空間復雜度：(O(1))，只使用了常數級的額外變量。
這種方法通過直接分析評分序列的上升和下降趨勢，避免了兩次遍歷，在邏輯上更加直觀，同時保持了線性的時間復雜度。
?
