题解 | #递增数组#

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

基于贪心的思想，对于已经递增的区间我们不应该去处理，为了减少后面的操作次数，所以对于整个数组我们需要进行一次遍历，只需要处理非递增的区间就可以解决问题，下面是完整代码：

class Solution {
public:
    long long IncreasingArray(vector<int>& array) {
        long long ans=0;//ans返回最后的返回次数
        for(int i=0;i<array.size()-1;i++){
            ans+=max(0,array[i]+1-array[i+1]);
        }
        return ans;
    }
};

时间复杂度： $O(n)$ 只需要对数组进行一次遍历即可
空间复杂度： $O(1)$ 不需要额外空间返回答案
优缺点：基于贪心实现，思路清晰，代码简单。
三.算法(java实现)
思路和算法二相似，都是基于贪心的思想，下面是完整代码：

import java.util.*;
public class Solution {
    public long IncreasingArray (int[] array) {
        long sum=0;
        for (int i = 1; i < array.size(); ++i) {
            if (array[i] <= array[i-1]) {
                sum+=array[i-1]-array[i] + 1;
            }
        }
        return sum;
    }
}

时间复杂度： $O(n)$ 只需要对数组进行一次遍历即可
空间复杂度： $O(1)$ 不需要额外空间返回答案
优缺点：基于贪心实现，思路清晰，代码简单。