期末考试结束后，小南老师决定根据每个同学的成绩给予适当的奖励，比如好 吃的糖果。分发糖果时，小南老师让所有同学站成一排，为了公平起见，分发要求如下： 每个同学至少分配到 1 个糖果；相邻两个同学中，成绩更高的同学会获得更多的糖果。 已知班上有 n 个同学，长度为 n 的整数数组 grades 表示每个同学的成绩。请你帮忙计 算小南老师需要准备的最少糖果数目。示例如下： 输入：grades = [1,0,2] 输出：5 解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。 请你帮忙设计一个贪心算法，并完成以下任务： (1) 描述算法思路，证明该问题的贪心选择性; (2) 给出伪代码，并分析算法的空间复杂度和空间复杂度

(1) 算法思路：首先，将每个同学初始化为至少分配一个糖果。然后，对每个同学进行遍历，如果当前同学的成绩比前一个同学高，则将当前同学分配到的糖果数目设为前一个同学分配的糖果数目加一；否则，将当前同学分配到的糖果数目设为一。接下来，对每个同学进行逆向遍历，如果当前同学的成绩比后一个同学高且分配的糖果数目不大于后一个同学，则将当前同学分配到的糖果数目设为后一个同学分配的糖果数目加一。最终，将每个同学分配到的糖果数目加起来，得到小南老师需要准备的最少糖果数目。

证明贪心选择性：对于每个同学，如果当前同学的成绩比前一个同学高，则贪心地让当前同学分配到的糖果数目比前一个同学多一，可以保证相邻两个同学中，成绩更高的同学获得更多的糖果。对于每个同学，如果当前同学的成绩比后一个同学高且分配的糖果数目不大于后一个同学，则贪心地让当前同学分配到的糖果数目比后一个同学多一，可以保证每个同学至少分配到一个糖果。因此，该算法具有贪心选择性。

(2) 伪代码：

initialize each student with 1 candy
for i from 1 to n-1 do
if grades[i] > grades[i-1] then
assign i with (i-1) + 1 candies
end if
end for
for i from n-2 downto 0 do
if grades[i] > grades[i+1] and assign i with candies is not greater than assign (i+1) with candies then
assign i with (i+1) + 1 candies
end if
end for
sum up all assigned candies

时间复杂度：O(n)

空间复杂度：O(n)（需要一个数组存储每个同学分配到的糖果数目）