2021/1/26 递增数组

题目描述

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

示例

输入

[1,2,1]

返回值

2

说明

把第三个数字+2可以构成1，2，3

解题思路

使用贪心算法。遍历数组 arr[len] ，第 i 次区间为 [i, len]，若 arr[i] < arr[i-1]，那么区间所有数增加直到arr[i] = arr[i-1] + 1。不过本质就是数组第 i 个数需要比 i - 1 大 1，所以我们在 arr[i] < arr[i-1] 处直接求两个元素之间的差即可。

Java代码实现

public class Solution {
    public long IncreasingArray (int[] array) {
        long count = 0;
        for (int i = 1; i < array.length; ++i) {
            if (array[i] <= array[i-1]) {
                count += array[i-1] - array[i] + 1;
            }
        }
        return count;
    }
}