题解 | #递增数组#

题目描述：牛牛有一个数组array，牛牛可以每次选择一个连续的区间，让区间的数都加1，他想知道把这个数组变为严格单调递增，最少需要操作多少次？
关键点：
每次选择一个连续的区间，区间的数一次性加1
数组元素必须严格单调递增，不能出现元素相等的情况

方法一：贪心
要使得整个数组严格单调递增，就需要数组中每个局部都递增，递增的局部不管，我们只关注递减的局部，对递减区间再从左到右不断分割至剩下两个元素，当从左到右遍历时,要让 $图片说明$ 恒成立，至少需要操作的次数是 $a[i]-a[i-1]+1，(1<=i<n)$ ，这样就从局部最优推到全局最优，每次操作次数累加得到结果。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 array
     * @return long长整型
     */
    public long IncreasingArray (int[] array) {
        // write code here
        long res=0;
        for(int i=1;i<array.length;i++){
            //当第i个数比第i-1个数小时，它所要加的次数是a[i]-a[i-1]+1
            if(array[i]<array[i-1])
                res+=array[i-1]-array[i]+1;
        }
        return res;
    }
}

复杂度：
时间复杂度：遍历数组一次， $O(n)$
空间复杂度：无额外空间， $O(1)$

方法二：动态规划
$dp[i]$ 表示每个从递减区间到单调递增区间所需要的最少操作次数，当所有的递减区间都变为单调递增区间时，整个数组也单调递增，dp表的元素之和即最优操作之和

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 array
     * @return long长整型
     */
    public long IncreasingArray (int[] array) {
        // write code here
        long res=0;
        long[]dp=new long[array.length];
        for(int i=1;i<array.length;i++){
            //当第i个数比第i-1个数小时，它所要加的次数是a[i]-a[i-1]+1
            if(array[i]<array[i-1])
                dp[i-1]=array[i-1]-array[i]+1;
        }//操作次数之和为最终结果
        for(int i=0;i<dp.length;i++){
            res+=dp[i];
        }
        return res;
    }
}

复杂度：
时间复杂度：遍历一遍数组， $O(n)$
空间复杂度： $dp$ 数组的大小不超过n， $O(n)$
(n为数组元素大小)