题解 | #递增数组#

思路

题目分析

1. 给出了一个数组，我们要将其变为严格单调递增的数组。
2. 我们可以采取的方式是：选定某个子区间的所有数字同时进行+1操作
3. 最终返回我们处理的次数

• 直观上，当我们发现array[i] >= array[i+1]的时候，需要将array[i+1]进行+1操作，使其比前一项大
• 但是这样的方法导致结果是处理次数不是最优的，因为我们忽略了每次可以同时处理一个子区间的所有数字
• 因此当array[i+1]在执行+1操作的时候，我们不要拉大array[i+1]和其后面的数字之间原本的差，也就是说我们要继续维护array[i+1]和其后面数字的相对差值，具体操作就是将array[i+1]及其以后的元素视作子区间，其子区间内的元素同时+1操作。
• 利用贪心算法获得最小的处理次数，优化动态规划思路

方法一：动态规划

• 动态规划分析，引入dp数组

#include<numeric>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector array
     * @return long长整型
     */
    long long IncreasingArray(vector<int>& array) {
        // write code here
        long long n = array.size();
        long long sum = 0;
        vector<long long> dp(n,0);
        for(long long i = 0; i < n-1; i++) {
            if(array[i+1] <= array[i]) {                // 判断下一项是否需要进行+1操作
                dp[i+1] = array[i] - array[i+1] + 1;    // 下一项比上一项小的情况下，两项差值累计
            }
            dp[i+1] += dp[i];                           // 累计到dp数组末项中
        }
        return dp[n-1];
    }
};

复杂度分析

• 时间复杂度：，采用了单层循环
• 空间复杂度：，dp数组引入额外空间

方法二：贪心方法

• 优化dp数组的空间

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector array
     * @return long长整型
     */
    long long IncreasingArray(vector<int>& array) {
        // write code here
        long long n = array.size();
        long long sum = 0;
        for(long long i = 0; i < n-1; i++) {
            if(array[i+1] < array[i]) {                // 判断下一项是否需要进行+1操作
                sum += array[i] - array[i+1] + 1;      // 下一项比上一项小的情况下，两项差值累计
            }
        }
        return sum;
    }
};

复杂度分析

• 时间复杂度：，采用了单层循环
• 空间复杂度：，未引入额外空间