2021-11-22：给定一个正数数组arr，表示每个小朋友的得

原创

福大大架构师每日一题

修改于 2021-11-23 00:46:01

2100

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2021-11-22：给定一个正数数组arr，表示每个小朋友的得分；

任何两个相邻的小朋友，如果得分一样，怎么分糖果无所谓，但如果得分不一样，分数大的一定要比分数少的多拿一些糖果；

假设所有的小朋友坐成一个环形，返回在不破坏上一条规则的情况下，需要的最少糖果数。

来自网易。

答案2021-11-22：

1.求最小值的序号。

2.最小值放首位两端，构造n+1的数组arr2。

3.从左往右遍历arr2。left数组。

4.从右往左遍历arr2。right数组。

5.遍历根据left和right序号相同位置求最大值，累加n次，就是需要返回的值。

时间复杂度：O((N)。

额外空间复杂度：O(N)。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    arr := []int{3, 2, 1, 2, 3}
    ret := minCandy(arr)
    fmt.Println(ret)
}

func minCandy(arr []int) int {
    if len(arr) == 0 {
        return 0
    }
    if len(arr) == 1 {
        return 1
    }
    n := len(arr)
    minIndex := 0
    for i := 0; i < n; i++ {
        if arr[i] <= arr[lastIndex(i, n)] && arr[i] <= arr[nextIndex(i, n)] {
            minIndex = i
            break
        }
    }

    nums := make([]int, n+1)
    for i := 0; i <= n; i, minIndex = i+1, nextIndex(minIndex, n) {
        nums[i] = arr[minIndex]
    }
    left := make([]int, n+1)
    left[0] = 1
    for i := 1; i <= n; i++ {
        left[i] = twoSelectOne(nums[i] > nums[i-1], left[i-1]+1, 1)
    }
    right := make([]int, n+1)
    right[n] = 1
    for i := n - 1; i >= 0; i-- {
        right[i] = twoSelectOne(nums[i] > nums[i+1], right[i+1]+1, 1)
    }
    ans := 0
    for i := 0; i < n; i++ {
        ans += getMax(left[i], right[i])
    }
    return ans
}

func nextIndex(i int, n int) int {
    return twoSelectOne(i == n-1, 0, (i + 1))
}

func lastIndex(i int, n int) int {
    return twoSelectOne(i == 0, (n - 1), (i - 1))
}

func getMax(a int, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}

func twoSelectOne(c bool, a int, b int) int {
    if c {
        return a
    } else {
        return b
    }
}