已知数组arr，生成一个数组out，out的每个元素必须大于等于1，当arr[cur]>arr[cur-1]时，out[cur]>out[cur-1]；当arr[cur]>arr[cur+1]时，out[cur]>out[cur+1]。求最小out的元素之和。比如[2,3,5,5,4]，生成数组是[1,2,3,2,1]，和是9。
1.从左往右遍历，生成left数组。当arr[cur]>arr[cur-1]时，left[cur]=left[cur-1]+1。其他情况，left[cur]=1。[2,3,5,5,4]的left数组是[1,2,3,1,1]。
2.从右往左遍历，生成right数组。当arr[cur]>arr[cur+1]时，right[cur]=right[cur+1]+1。其他情况，right[cur]=1。[2,3,5,5,4]的right数组是[1,1,1,2,1]。
3.生成数组out，out数组的i位置元素是left数组i位置元素和right数组i位置元素的最大值。[2,3,5,5,4]的out数组是[1,2,3,2,1]。
4.求数组out的累加和，这个累加和就是需要的返回值。
5.时间复杂度O(N)。空间复杂度O(N)。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
arr := []int{2, 3, 5, 5, 4}
ret := candy1(arr)
fmt.Println(ret)
}
// 这是原问题的优良解
// 时间复杂度O(N)，额外空间复杂度O(N)
func candy1(arr []int) int {
if len(arr) == 0 {
return 0
}
N := len(arr)
left := make([]int, N)
for i := 1; i < N; i++ {
if arr[i-1] < arr[i] {
left[i] = left[i-1] + 1
}
}
right := make([]int, N)
for i := N - 2; i >= 0; i-- {
if arr[i] > arr[i+1] {
right[i] = right[i+1] + 1
}
}
ans := 0
for i := 0; i < N; i++ {
ans += getMax(left[i], right[i])
}
return ans + N
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}执行结果如下：
![2021-06-18：已知数组arr，生成一个数组out，out的每个元素必须大于等于1，当arr[cur]＞arr[cur-1]时，out[cur]＞out[cur-1]；当arr[cur]＞arr](https://ctyun-collect-0531.gdoss.xstore.ctyun.cn/files/2023/05/23/b454dcd732a442788e00782951c72871.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=/resize,m_fixed,w_1184 "2021-06-18：已知数组arr，生成一个数组out，out的每个元素必须大于等于1，当arr[cur]＞arr[cur-1]时，out[cur]＞out[cur-1]；当arr[cur]＞arr")
