一. 簡介

本文記錄力扣網上涉及數組方面的編程題：分發糖果。

這里使用貪心算法的思路來解決（求局部最優，最終求全局最優解）：每個孩子只需要考慮與相鄰孩子的相對關系。

二.?力扣網編程135題：分發糖果（遍歷兩遍數組）

n 個孩子站成一排。給你一個整數數組 ratings 表示每個孩子的評分。
你需要按照以下要求，給這些孩子分發糖果：
每個孩子至少分配到 1 個糖果。
相鄰兩個孩子評分更高的孩子會獲得更多的糖果。
請你給每個孩子分發糖果，計算并返回需要準備的 最少糖果數目 。

示例 1：
輸入：ratings = [1,0,2]
輸出：5
解釋：你可以分別給第一個、第二個、第三個孩子分發 2、1、2 顆糖果。

示例 2：
輸入：ratings = [1,2,2]
輸出：4
解釋：你可以分別給第一個、第二個、第三個孩子分發 1、2、1 顆糖果。
第三個孩子只得到 1 顆糖果，這滿足題面中的兩個條件。

解題思路一：（遍歷兩遍數組）

我們可以將「相鄰的孩子中，評分高的孩子必須獲得更多的糖果」這句話拆分為兩個規則，分別處理：

左規則：ratings[i-1] < ratings[i]，i號孩子的糖果比 i-1號孩子的糖果數量多；

右規則：ratings[i] > ratings[i+1]，i號孩子比 i+1號孩子的糖果數量少；

遍歷該數組兩次，處理出每一個學生分別滿足左規則或右規則時，最少需要被分得的糖果數量。每個人最終分得的糖果數量即為這兩個數量的最大值。

具體方法如下：

1. 定義一個數組left[ratingsSize]，用于存放滿足左規則的糖果數目；變量 right 存放滿足右規則的糖果數目；

1. 滿足左規則：從前往后遍歷數組，若 ratings[i-1] < ratings[i]，則 left[i] = left[i-1] +1，否則，left[i] = 1；

2. 滿足右規則：類似處理，不過是從后往前進行遍歷。

若 ratings[i] > ratings[i+1]，則 right += 1，否則，right =1。在遍歷過程中，求 滿足左規則和右規則的糖果數目進行比較，求最大值，同時進行累計。

C語言實現如下：

//遍歷兩次數組，滿足條件
//1.左規則：ratings[i-1] < ratings[i], 則ratings[i]=ratings[i-1]+1
//2.右規則：ratings[i] > ratings[i+1],則ratings[i]= ratings[i+1]+1
int candy(int* ratings, int ratingsSize) {int i;int count = 0;int left[ratingsSize];//從前往后遍歷//左規則：ratings[i-1] < ratings[i], 則ratings[i]=ratings[i-1]+1for(i = 0; i < ratingsSize; i++) {if((i>0) && (ratings[i-1] < ratings[i])) {left[i] = left[i-1]+1;}else {left[i] = 1;}}int right = 0;//從后往前遍歷//右規則：ratings[i] > ratings[i+1],則ratings[i]= ratings[i+1]+1for(i = ratingsSize-1; i >= 0; i--) {if((i < ratingsSize-1) && (ratings[i] > ratings[i+1])) {right += 1;} else {right = 1;}count += fmax(left[i], right);} return count;
}

可以看出，貪心算法的解法的時間復雜度為 O(n)，空間負責度為O(n)。

第二種實現如下，也是同樣的思路（貪心算法）：

//貪心算法：
//局部最優：每個孩子只需要關心和她相鄰的關系
int candy(int* ratings, int ratingsSize) {int i;int candies[ratingsSize];int right = 0;int count = 0;memset(candies, 0, ratingsSize*sizeof(int));for(i = 0; i < ratingsSize; i++) {candies[i] = 1;}//遵循左規則：從左到右遍歷//如果 ratings[i-1] < ratings[i]for(i = 0; i < ratingsSize; i++) {if((i>0) && (ratings[i-1] < ratings[i])) {candies[i] = candies[i-1] + 1;}}//遵循右規則：從右向左遍歷//如果 ratings[i] > ratings[i+1]for(i = ratingsSize-1; i>=0; i--) {if((i<ratingsSize-1) && (ratings[i] > ratings[i+1])) {right += 1;}else {right = 1;}count += fmax(candies[i], right);}return count;
}