2022-01-12：给定一个正数数组arr，长度为n，下标0~n-1， arr中的0、n-1位置不需要达标，它们分别是最左、最右的位置， 中间位置i需要达标，达标的条件是 : arr[i-1] ＞

2022-01-12：给定一个正数数组arr，长度为n，下标0~n-1，
arr中的0、n-1位置不需要达标，它们分别是最左、最右的位置，
中间位置i需要达标，达标的条件是 : arr[i-1] > arr[i] 或者 arr[i+1] > arr[i]哪个都可以。
你每一步可以进行如下操作：对任何位置的数让其-1，
你的目的是让arr[1~n-2]都达标，这时arr称之为yeah！数组。
返回至少要多少步可以让arr变成yeah！数组。
数据规模 : 数组长度 <= 10000，数组中的值<=500。
来自360面试。

答案2022-01-12：

方法一、动态规划。
方法二、贪心。
时间复杂度：O(N)。
空间复杂度：O(N)。

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

package main

import (

    "fmt"

    "math"

)

func main() {

    if true {

        arr := []int{3, 2, 1, 2, 4, 4}

        ret := minCost1(arr)

        fmt.Println(ret)

    }

    if true {

        arr := []int{3, 2, 1, 2, 4, 4}

        ret := yeah(arr)

        fmt.Println(ret)

    }

}

const INVALID = math.MaxInt64

// 递归方法，已经把尝试写出

func minCost1(arr []int) int {

    if len(arr) < 3 {

        return 0

    }

    min := INVALID

    for _, num := range arr {

        min = getMin(min, num)

    }

    for i := 0; i < len(arr); i++ {

        arr[i] += len(arr) - min

    }

    return process1(arr, 1, arr[0], true)

}

// 当前来到index位置，值arr[index]

// pre : 前一个位置的值，可能减掉了一些，所以不能用arr[index-1]

// preOk : 前一个位置的值，是否被它左边的数变有效了

// 返回 : 让arr都变有效，最小代价是什么？

func process1(arr []int, index, pre int, preOk bool) int {

    if index == len(arr)-1 { // 已经来到最后一个数了

        if preOk || pre < arr[index] {

            return 0

        } else {

            return INVALID

        }

        //return preOk || pre < arr[index] ? 0 : INVALID;

    }

    // 当前index，不是最后一个数！

    ans := INVALID

    if preOk {

        for cur := arr[index]; cur >= 0; cur-- {

            next := process1(arr, index+1, cur, cur < pre)

            if next != INVALID {

                ans = getMin(ans, arr[index]-cur+next)

            }

        }

    } else {

        for cur := arr[index]; cur > pre; cur-- {

            next := process1(arr, index+1, cur, false)

            if next != INVALID {

                ans = getMin(ans, arr[index]-cur+next)

            }

        }

    }

    return ans

}

// 最终的最优解，贪心

// 时间复杂度O(N)

// 请注意，重点看上面的方法

// 这个最优解容易理解，但让你学到的东西不是很多

func yeah(arr []int) int {

    if len(arr) < 3 {

        return 0

    }

    n := len(arr)

    nums := make([]int, n+2)

    nums[0] = math.MaxInt64

    nums[n+1] = math.MaxInt64

    for i := 0; i < len(arr); i++ {

        nums[i+1] = arr[i]

    }

    leftCost := make([]int, n+2)

    pre := nums[0]

    change := 0

    for i := 1; i <= n; i++ {

        change = getMin(pre-1, nums[i])

        leftCost[i] = nums[i] - change + leftCost[i-1]

        pre = change

    }

    rightCost := make([]int, n+2)

    pre = nums[n+1]

    for i := n; i >= 1; i-- {

        change = getMin(pre-1, nums[i])

        rightCost[i] = nums[i] - change + rightCost[i+1]

        pre = change

    }

    ans := math.MaxInt64

    for i := 1; i <= n; i++ {

        ans = getMin(ans, leftCost[i]+rightCost[i+1])

    }

    return ans

}

func getMin(a, b int) int {

    if a < b {

        return a

    } else {

        return b

    }

}

执行结果如下：

左神java代码

2022-01-12：给定一个正数数组arr，长度为n，下标0~n-1， arr中的0、n-1位置不需要达标，它们分别是最左、最右的位置， 中间位置i需要达标，达标的条件是 : arr[i-1] ＞的相关教程结束。