2022-01-12:给定一个正数数组arr,长度为n,下标0n-1,
arr中的0、n-1位置不需要达标,它们分别是最左、最右的位置,
中间位置i需要达标,达标的条件是 : arr[i-1] > arr[i] 或者 arr[i+1] > arr[i]哪个都可以。
你每一步可以进行如下操作:对任何位置的数让其-1,
你的目的是让arr[1n-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
}
}
执行结果如下: