题解 | #递增数组#

思路：

题目的主要信息：

给定一个数组，每次操作选择数组中一个区间的所有数字加1
使区间严格单调递增最少需要多少次操作

因为要严格单调递增，所以前一个数一定比后一个数字大，我们假设 $a[1] - a[0] = 1$ ，那么我们只需要给 $a[1]+2$ 即可严格大于，但是后面的数字因为 $a[1]$ 的增加，需要严格单调也可能会要增加操作，刚好我们可以选择一个区间，因此我们每次区间可以选择成要递增这个数到数组结尾。

方法一：动态规划
具体做法：
用一个数组记录前一个元素比后一个元素大的差值，因为相等也不行，所以差值还要再加1。最后遍历数组将所有差值相加即可。

class Solution {
public:
    long long IncreasingArray(vector<int>& array) {
        long long res = 0;
        vector<long long> dp(array.size() + 1, 0); //记录数组之间的差值
        for(int i = 1; i < array.size(); i++) //遍历数组
            if(array[i] <= array[i - 1])  //有差值
                dp[i] = array[i - 1] - array[i] + 1; //需要操作插值这么多次
        for(int i = 0; i < dp.size(); i++)
            res += dp[i];
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，单独遍历两次，每次都为 $O(n)$
空间复杂度： $O(n)$ ，辅助数组dp的空间

方法二：贪心
具体做法：
方法一的辅助数组可以省略，我们可以利用贪心思想直接在第一次循环中将所有差值相加。
图片说明
C++版本

class Solution {
public:
    long long IncreasingArray(vector<int>& array) {
        long long res = 0;
        for(int i = 1; i < array.size(); i++) //遍历数组
            if(array[i] <= array[i - 1])  //有差值
                res += array[i - 1] - array[i] + 1; //需要操作插值这么多次
        return res;
    }
};

Java版本

import java.util.*;

public class Solution {
    public long IncreasingArray (int[] array) {
        long res = 0;
        for(int i = 1; i < array.length; i++) //遍历数组
            if(array[i] <= array[i - 1])  //有差值
                res += array[i - 1] - array[i] + 1; //需要操作插值这么多次
        return res;
    }
}

Python版本

class Solution:
    def IncreasingArray(self , array ):
        n = len(array)
        res = 0
        for i in range (1, n): #遍历数组
            if array[i] <= array[i - 1]:
                res = res + array[i - 1] - array[i] + 1 #差值相加
        return res

复杂度分析：

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