問題：

老師想給孩子們分發糖果，有 N 個孩子站成了一條直線，老師會根據每個孩子的表現，預先給他們評分。

需要按照以下要求，幫助老師給這些孩子分發糖果：

每個孩子至少分配到 1 個糖果。

評分更高的孩子必須比他兩側的鄰位孩子獲得更多的糖果。

那么這樣下來，老師至少需要準備多少顆糖果呢？

示例 1：

輸入：[1,0,2]

輸出：5

解釋：你可以分別給這三個孩子分發 2、1、2 顆糖果。

示例 2：

輸入：[1,2,2]

輸出：4

解釋：你可以分別給這三個孩子分發 1、2、1 顆糖果。

第三個孩子只得到 1 顆糖果，這已滿足上述兩個條件。

解答思路：

以下是使用 Java 語言解決此問題的代碼：

import java.util.ArrayList;import java.util.List;public class CandyDistribution {public static void main(String[] args) {int[] ratings = {1, 0, 2};System.out.println(distributeCandies(ratings));}public static int distributeCandies(int[] ratings) {List<Integer> candies = new ArrayList<>();for (int i = 0; i < ratings.length; i++) {candies.add(1);}for (int i = 1; i < ratings.length; i++) {if (ratings[i] > ratings[i - 1]) {candies.set(i, candies.get(i - 1) + 1);} else if (ratings[i] < ratings[i - 1]) {int j = i;while (j > 0 && ratings[j] < ratings[j - 1] && candies.get(j) >= candies.get(j - 1)) {candies.set(j - 1, candies.get(j) + 1);j--;}}}int sum = 0;for (Integer candy : candies) {sum += candy;}return sum;}}

這段代碼首先初始化一個包含每個孩子 1 顆糖果的列表。然后，它遍歷評分數組。如果當前孩子的評分高于前一個孩子的評分，它會將當前孩子的糖果數增加 1。如果當前孩子的評分低于前一個孩子的評分，它會從后往前找到第一個評分高于當前孩子的孩子，并將該孩子的糖果數增加 1。最后，它計算并返回糖果總數。

這段代碼的時間復雜度為 O(n)，其中 n 是孩子的數量，因為它只需要遍歷評分數組一次。空間復雜度也為 O(n)，因為它需要創建一個新的列表來存儲每個孩子的糖果數。

(文章為作者在學習java過程中的一些個人體會總結和借鑒，如有不當、錯誤的地方，請各位大佬批評指正，定當努力改正，如有侵權請聯系作者刪帖。)