题解 | #递增数组#

题目描述
牛牛有一个数组array，牛牛可以每次选择一个连续的区间，让区间的数都加1，他想知道把这个数组变为严格单调递增，最少需要操作多少次？

方法一：贪心思想求解

求解思路
对于本题目要求整个数组为严格单调递增数组，那么数组的局部肯定都是递增的，否则这个数组不是递增数组。我们对数组的递减部分进行处理，采用贪心的思想进行元素交换，是的递减的部分变为递增，这样一步步地操作，最终即可得出本题的答案。

图片说明

解题代码

import java.util.*;
public class Solution {
    public long IncreasingArray (int[] array) {
        long myres=0; // 声明变量，记录结果
        for(int i=1;i<array.length;i++)
        {   //当第i个数比第i-1个数小时，它所要加的次数是a[i]-a[i-1]+1
            if(array[i]<array[i-1])
                myres+=array[i-1]-array[i]+1;
        }
        return myres; // 返回结果
    }
}

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：没有引入额外的内存地址空间，因此空间复杂度为 $O(1)$

方法二：动态规划思想求解

求解思路
对于本题目我们可以采用动态规划思想来进行求解，我们定义dp[i]表示从递减区间到递增区间所需要的最少操作次数，当所有的递减区间都变为单调增区间之后，我们对dp数组进行求和，即可得到本题目的答案。

图片说明

解题代码

import java.util.*;
public class Solution {
    public long IncreasingArray (int[] array)
    {
        long myres=0; // 声明结果
        long[]mydp=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])
                mydp[i-1]=array[i-1]-array[i]+1;
        }
        for(int i=0;i<mydp.length;i++)
        {   //操作次数之和为最终结果
            myres+=mydp[i];
        }
        return myres; // 返回结果即可
    }
}

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：使用数组dp[N],使用额外的内存地址空间，因此空间复杂度为 $O(N)$