2022-01-12: give a positive array arr, length N, subscript 0~n-1, a

2022-01-12： Given an array of positive numbers arr, The length is n, Subscript 0~n-1,

arr Medium 0、n-1 The location does not need to be up to standard , They are the leftmost 、 Rightmost position ,

In the middle i Need to reach the standard , The conditions for reaching the standard are : arri-1 > arri perhaps arri+1 > arri Any one can .

You can do the following at each step ： Let the number at any position be -1,

Your aim is to make arr1~n-2 All up to standard , At this time arr be called yeah！ Array .

Return to at least how many steps can make arr become yeah！ Array .

Data scale : The length of the array <= 10000, The values in the array <=500.

come from 360 interview .

answer 2022-01-12：

Method 1 、 Dynamic programming .

Method 2 、 greedy .

Time complexity ：O(N).

Spatial complexity ：O(N).

The code to use golang To write . The code is as follows ：

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

//  Recursive method , The attempt has been written out 
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)
}

//  Now comes index Location , value arr[index]
// pre :  The value of the previous position , Maybe you lost some , So it can't be used arr[index-1]
// preOk :  The value of the previous position , Is it valid by the number on its left 
//  return  :  Give Way arr All become effective , What is the minimum cost ？
func process1(arr []int, index, pre int, preOk bool) int {
    if index == len(arr)-1 { //  It's the last count 
        if preOk || pre < arr[index] {
            return 0
        } else {
            return INVALID
        }
        //return preOk || pre < arr[index] ? 0 : INVALID;
    }
    //  At present index, Not the last number ！
    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
}

//  The final optimal solution , greedy 
//  Time complexity O(N)
//  Please note that , Focus on the above methods 
//  This optimal solution is easy to understand , But you don't learn much 
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
    }
}

The results are as follows ：

picture

Zuo Shen java Code