递增数组

[编程题]递增数组

热度指数：3412 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

示例1

输入

[1,2,1]

输出

说明

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

备注:

$1 \leq array.size \leq 2*10^{5}$

$1 \leq array[i] \leq 1*10^{9}$

算法知识视频讲解

JavaScript

小白不黑爱吃糖

/**
  * 
  * @param array int整型一维数组 array
  * @return long长整型
  */
function IncreasingArray( array ) {
    // write code here
    var count=0;//计数
    var p;//暂存
    for(let i=1;i<array.length;i++){
        if(array[i]<=array[i-1]){//比直接左边数值小，就要计数
            p=array[i-1]+1-array[i];//严格递增，+1：把相等的情况跳过去
            count+=p;
            
        }
    }
    return count;
}
module.exports = {
    IncreasingArray : IncreasingArray
};

个人分析思路：

在理解该题的时候有个严重的误区，会认为每次操作改变了数组的值，其实没有，该题只需要考虑需要做多少次变换，而不是做变换！！

eg：1 3 2 7 6 4 2

对于该例，2->4 2次

6->8 2次

之前，我会自己把数组内容变换为操作之后，所以对于解题思路有一定误解，了解清楚，不需要改变值后

其实对于后面的6 4 2 之间的差值已经是固定的，即当6->7 则4->5,2->3这是可以一起变化的，最终都是要看比直接左边的数据相差多少

对于例子：1 3 2 7 6 9 10：既可以认为对6单独进行了两次加1，也可以认为对6 9 10三个数进行了两次的区间加1即 8 11 12，这样对于后面也是递增的是不会有影响的

观点可能有误，望指正。

发表于 2020-08-18 11:42:49 回复(0)

JavaScript

萌萌萌哒

🧐js怎么不支持BigInt? @牛客出题人

数据在本地测了没问题啊

function IncreasingArray(arr) {
    let cnt = BigInt(0)
    arr.map(e=> BigInt(e))
    for (let i = 0; i < arr.length-1; i++) {
        if(BigInt(arr[i])>BigInt(arr[i+1])) cnt += (BigInt(arr[i])-BigInt(arr[i+1]) + 1n)
    }
    return cnt
}
module.exports = {
    IncreasingArray : IncreasingArray
};

编辑于 2020-03-17 12:09:28 回复(0)