牛客网: BM95
题目: 每个孩子至少一个糖果,相邻孩子中得分高的至少多一些,最少多少糖果。
思路: 初始化candy数组元素全为1,从1往右遍历,arr[i]>arr[i-1], 需要candy[i]=candy[i-1]+1;total = candy[n-1], 从右往左遍历,arr[i-1]>arr[i], candy[i-1]<=candy[i]则更新candy[i-1]=candy[i]+1,同时累加到total。
代码:
// gopackage main
// import "fmt"/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** pick candy* @param arr int整型一维数组 the array* @return int整型
*/
func candy( arr []int ) int {// write code herecandy := make([]int, len(arr))for i := 0; i < len(arr); i++ {candy[i] = 1}for i := 1; i < len(arr); i++ {if arr[i] > arr[i-1] {candy[i] = candy[i-1] + 1}}total := candy[len(candy)-1]for i := len(candy)-1; i > 0; i-- {if arr[i-1] > arr[i] && candy[i-1] <= candy[i] {candy[i-1] = candy[i] + 1}total += candy[i-1]}return total}