首页 > 试题广场 >

递增数组

[编程题]递增数组
  • 热度指数：3412 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
牛牛有一个数组array，牛牛可以每次选择一个连续的区间，让区间的数都加1，他想知道把这个数组变为严格单调递增，最少需要操作多少次？
示例1

输入

[1,2,1]

输出

2

说明

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

备注:
算法知识视频讲解
添加回答
Resolmi头像 Resolmi
虽然是easy，还是想了一会儿，我的想法就是当增加一个数的时候就连同后面的所有数一起增加，而增加一个数肯定是增加到前一个数+1的次数是最少的（当然我们也不用真的去加，因为后面的区间是整体++，而我们要求的操作次数只是个差值）
其实很详细的证明我也给不出来，我只考虑了几种情况
  1. i 后面的部分是单调递增的 3 1(i)  2  3，那么很明显这里和后面一起增加是最优选择
  2. i 后面是部分是单调递减的 3 3(i)  2  1，那么同样，和后面的一起增加是最优选择，单独选择某一个区间都会导致整体的落差变大，使得后面没增加的部分需要增加的次数增加
  3. i 后面先递增后递减 3 1(i)  2  1 同上 相当于 递增+递减 看做两部分，（1 2）同增，那么（2，1）也应该随之同增
  4. i 后面先递减后递增 5 4(i) 3 5  递减+递增 也分成两部分 
public long IncreasingArray (int[] array) {
    // write code here
    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;
}


编辑于 2020-08-31 00:11:18 回复(0)
白色纯度头像 白色纯度
python： 
class Solution:
    def IncreasingArray(self , array ):
        res = 0
        for i in range(1,len(array)):
            diff = array[i]-array[i-1]
            if diff < 0:
                res += 1 - diff
        return res
答案是看了各位网友的讨论之后才写的，几乎是抄袭，比较简洁。也可以直接用一行代码解决，如下： 
class Solution:
    def IncreasingArray(self , array ):
        return sum([1-array[i]+array[i-1] for i in range(1,len(array)) if array[i]-array[i-1]<0])
思路：
看到有人说，同时增加一段区间内相同的高度无法影响这段区间内的单调性，然后直接说最优方案就是一个一个的增高。这句话不假，但是要作为用贪心算法的理由，显然有点让人摸不到头脑。首先强调第一个事实，最优意味着次数最少！
算法介绍：
1. diff定义：右边与左边数值的差。diff>0，则符合条件，不用进行任何操作，diff<=0,不符合条件，需要进行增值操作，对右边的值增加1-diff的高度，这样就能符合严格递增的规则。
2. 严格递增是从整体的布局考虑，而代码实际的操作却是相邻两个值在规则下的矫正，即全局最优方案就是每个局部最优方案的整合，也就是说贪心算法就是最优解决方案。局部最优如何能成为全局最优？ 事实上，diff<0时，需要对右边的值进行增高，因此每当遇到左边高于右边的情况，我们势必要对这种情况进行增高处理。这样，每次的增高处理都将右边值之后的所有数进行了增高操作，那么数值的单调性并未发生任何改变，相邻数字的高度差也没发生任何改变。只需在遇到增高的情况时，将右边值之后的所有数进行1-diff的必要增高操作，那么最终计算出来的次数就是最优答案。注意 必要 两个字就是贪心算法能成为全局最优算法的核心！
做题误区：
3. 最后，强调一个我做题时遇到的误区，将最优理解为 最少增高的数值，这样的理解对做题非常不利。比如【1，3，2，7，6，4，2】，这样的一个数组，我的第一反应居然是把它变为一个最优的单调数组，即【1，3，4，7，8，9，10】。这个显然对题目的理解有失偏颇，正确的做法是：【1，3，4，9，8，6，4】——>【1，3，4，9，10，6，4】——>【1，3，4，9，10，11，9】——>【1，3，4，9，10，11，12】
一共操作了12次，即为最优操作。如果理解为我刚刚的错误想法，那么需要操作的次数就是17次，显然不是最优。
发表于 2020-07-31 22:58:19 回复(4)
C/C++
nbgao头像 nbgao 
class Solution {
public:
    /**
     * 
     * @param array int整型vector array
     * @return long长整型
     */
    long long IncreasingArray(vector<int>& array) {
        long long s = 0;
        for(int i=1;i<array.size();i++){
            if(array[i]<array[i-1])
                s += array[i-1] - array[i] + 1;
        }
        return s;
    }
};

发表于 2020-06-19 01:39:29 回复(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)
在研究求职打法的长颈鹿很想去三亚看海头像 在研究求职打法的长颈鹿很想去三亚看海
class Solution {
public:
    /**
     * 
     * @param array int整型vector array
     * @return long长整型
     */
    long long IncreasingArray(vector<int>& array) {
        // write code here
        long long s=0;
        for(int i=1;i<array.size();i++){
            int temp=0;
            while(array[i]+temp<=array[i-1]){
                temp++;
            }
            array[i]+=temp;
            s+=temp;
        }
        return s;
    }
};
为什么我这个代码通过不了
发表于 2020-10-14 22:27:48 回复(0)
Java
李寻七头像 李寻七
public class Solution {
    public long IncreasingArray (int[] array) {
        // write code here
         long ans=0;
        for(int i=0;i<array.length-1;i++)
            if(array[i]<array[i+1])
                continue;
            else
                ans+=array[i]+1-array[i+1];                
        return ans;
    }
}
发表于 2020-10-13 20:38:13 回复(0)
Python
牛客88675210号头像 牛客88675210号
class Solution:
    def IncreasingArray(self , array ):
        sum1=0
        for i in range(len(array)-1):
            if array[i]>=array[i+1]:
                sum1+=array[i]-array[i+1]+1
        return sum1
发表于 2020-10-09 16:58:50 回复(1)
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)
復活の検事头像 復活の検事 
import java.util.*;


public class Solution {
    /**
     *
     * @param array int整型一维数组 array
     * @return long长整型
     */
    public long IncreasingArray (int[] array) {
        long result = 0;
        for(int i=0;i<array.length-1;i++){
            if(array[i+1] <= array[i]){
                int sub = array[i] - array[i+1] + 1;
                result += sub;
            }
        }

        return result;
    }
}

发表于 2020-08-08 17:08:17 回复(0)
Unlimited_Blade_Works头像 Unlimited_Blade_Works
  • 首先，对于任意一个序列，我们都可按递增递减（包括非严格的）的方式将序列分成不同的组。如[7,4,3,1,2,9,8]，我们可以分成[7,4,3,1]，[2,9]，[8]。
  • 先不考虑太复杂，我们单独对每种类型（递增和递减）的组进行分析。显然地，递增的组我们无需进行操作。对于递减的组，最优的操作应该是让序列最终变为[a[0],a[0]+1,...,a[0]+x],这样对于后面的数字来说增加的1较少，那么这一变化会需要多少操作次数呢？直观上来看，显然为a[0]+x-a[x]，即最小的元素需要的操作次数。
  • 单独的操作分析完成后，我们需要考虑这些子数组组合在一起的情况。假设前部分子数组为A，长为n，后部分子数组为B，长为m。
  1. 若A[n-1]<B[0]，那么假设经过一系列操作使得A为递增，此时A变为A'。
    (1) 若A'[n-1]<B[0]，那么B数组单独处理即可。
    (2) 若A'[n-1]>=B[0]，那么只需要将B数组整体提升A[n-1]+1-B[0]，然后单独处理B即可。注意是A[n-1]而非A'[n-1]。因为在使得A为递增时，由于B和A相连，可以将操作区间扩大到A+B，使得在A变为递增时，B和A的相对差不变。
  2. 否则：这种情况和1中(2)的情况相同。先单独处理A，然后同样把B整体提升A[n-1]+1-B[0]，然后单独处理B即可。
  • 根据上述分析，我们发现组间若需要调整，那么整体提升的值为A[n-1]+1-B[0]。而组内的操作次数为a[0]+x-a[x]=a[0]+1-a[1] + a[1] +1-a[2] +..+a[x-1]+1-a[x]，即可以把组内操作转化为前一个值+1和后一个值的差，这就和组间的操作数的计算方法统一了。这样我们就无需分组内还是组间，最终答案就是sum(max(a[i]+1-a[i+1],0))，0<=i<n-1 

#define ll long long
 
class Solution {
public:
    /**
     *
     * @param array int整型vector array
     * @return long长整型
     */
    long long IncreasingArray(vector<int>& a) {
        // write code here
        int n = a.size();
        ll res = 0;
        for(int i=1;i<n;i++){
            res+=max(a[i-1]+1-a[i],0);
        }
        return res;
    }
};

编辑于 2020-07-14 10:00:51 回复(0)
繁星似尘头像 繁星似尘 
每次选择一个区间，其实只能改变区间端点处的单调性，区间内部的单调性无法改变，
并且右端点还可能由递增变为两数相等
所以，每次让一个数增加，其实就是最优化的方案
long long IncreasingArray(vector<int>& array) {
    long long res = 0;
    for(int i=1;i<array.size();i++){
        int difference = array[i] - array[i-1];
        if(difference <= 0){
            res += 1 - difference;
        }
    }
    return res;
}

编辑于 2020-06-06 10:08:24 回复(0)
C/C++
dong_feng头像 dong_feng
因为是可以每次选择一个连续的区间进行添加的，那么只要在一个连续的区间增加的次数是单调不减的就可以视为连续区间添加，添加次数就是最大值。

class Solution {
public:
    /**
     * 
     * @param array int整型vector array
     * @return long长整型
     */
    long Maxnum(long a,long b)
    {
        if(a>b)
            return a;
        return b;
    }
    
    long long IncreasingArray(vector<int>& array) {
        // write code here 
        if(array.size()==0||array.size()==1)return 0;
        long long res=0;
        for(int i=1;i<array.size();i++)
        {
               if(array[i]<=array[i-1])//找到不符合的点
               {
                   long num =array[i-1]-array[i]+1; //计算该点的增加次数
                   for(int j=i+1;j<array.size()+1;j++)//向后找
                   {
                       if(j==array.size())
                       {
                           i=j;
                           break;
                       }
                      //这个因为是严格递增，那么第j个数一定比第i个数至少大j-i+1（j>i），判断逻辑反过来写
                      //并且计算该点增加次数要不小于前面的增加次数。
                       if(array[j]-j+i<=array[i-1]          
                          && num<=array[i-1]-array[j]+j-i+1)
                           num= array[i-1]-array[j]+j-i+1;
                       else
                       {
                           i=j;
                           break;
                       }
                   }
                   res+=num;
               }
        }
        return res;
    }
};
发表于 2020-04-07 00:26:17 回复(0)
提交观点

问题信息

贪心 数组
难度：
12条回答 5601浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号