2021-06-18:已知数组arr,生成一个数组out,out的每个元素必须大于等于1,当arr[cur]>arr[cur-1]时,out[cur]>out[cur-1];当arr[cur]>arr...求最小out的元素之和。比如[2,3,5,5,4],生成数组是[1,2,3,2,1],和是9。
福大大 答案2021-06-18:
1.从左往右遍历,生成left数组。...[2,3,5,5,4]的left数组是[1,2,3,1,1]。
2.从右往左遍历,生成right数组。当arr[cur]>arr[cur+1]时,right[cur]=right[cur+1]+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编写。