2021-06-18：已知数组arr，生成一个数组out，out的每个元素必须大于等于1，当arr[cur]＞arr[cur-1

福大大架构师每日一题

发布于 2021-08-05 16:11:02

3900

发布于 2021-08-05 16:11:02

2021-06-18：已知数组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。

福大大答案2021-06-18：

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
    }
}

执行结果如下：