首页 > 试题广场 >

递增数组

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

输入

[1,2,1]

输出

2

说明

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

备注:
算法知识视频讲解
开通博客
头像 Tag_Kausal
发表于 2020-02-13 17:28:52
因为我们要求得一个单调递增的序列，那么我们如果要选择一个区间的话这个区间必为后缀，不然我们选择一个中间的区间相当于把中间提高了，那么对后面就造成了不利的影响。所以我们只需要看每一个位置i与后面的一个元素i+1的差，位置i的贡献为max(0,array[i]+1-array[i+1])。时间复杂度O( 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 未来0116
发表于 2021-08-04 21:55:10
一.题目描述NC531递增数值牛牛有一个数组array，牛牛可以每次选择一个连续的区间，让区间的数都加1，他想知道把这个数组变为严格单调递增，最少需要操作多少次？二.算法(贪心)基于贪心的思想，对于已经递增的区间我们不应该去处理，为了减少后面的操作次数，所以对于整个数组我们需要进行一次遍历，只需要处 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 小兄弟加油啊
发表于 2021-10-29 10:38:01
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param array int整型vector array * @return long长 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 球球了给孩子一个offer吧
发表于 2021-08-07 10:52:46
题目描述：牛牛有一个数组array，牛牛可以每次选择一个连续的区间，让区间的数都加1，他想知道把这个数组变为严格单调递增，最少需要操作多少次？关键点：每次选择一个连续的区间，区间的数一次性加1数组元素必须严格单调递增，不能出现元素相等的情况 方法一：贪心要使得整个数组严格单调递增，就需要数组中每个局 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 馒头2020
发表于 2021-01-26 11:24:28
题目描述 牛牛有一个数组array，牛牛可以每次选择一个连续的区间，让区间的数都加1，他想知道把这个数组变为严格单调递增，最少需要操作多少次？ 示例 输入 [1,2,1] 返回值 2 说明 把第三个数字+2可以构成1，2，3 解题思路 使用贪心算法。遍历数组 arr[len] ，第 i 次区间为 [ 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 摸鱼学大师
发表于 2021-08-05 13:01:07
思路： 题目的主要信息： 给定一个数组，每次操作选择数组中一个区间的所有数字加1 使区间严格单调递增最少需要多少次操作 因为要严格单调递增，所以前一个数一定比后一个数字大，我们假设，那么我们只需要给即可严格大于，但是后面的数字因为的增加，需要严格单调也可能会要增加操作，刚好我们可以选择一个区间， 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 认认真真coding
发表于 2021-08-08 16:16:13
题目描述牛牛有一个数组array，牛牛可以每次选择一个连续的区间，让区间的数都加1，他想知道把这个数组变为严格单调递增，最少需要操作多少次？ 方法一：贪心思想求解 求解思路对于本题目要求整个数组为严格单调递增数组，那么数组的局部肯定都是递增的，否则这个数组不是递增数组。我们对数组的递减部分进行处理， 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 不会做题的小菜鸡
发表于 2021-09-15 15:10:36
思路 题目分析 给出了一个数组，我们要将其变为严格单调递增的数组。 我们可以采取的方式是：选定某个子区间的所有数字同时进行+1操作 最终返回我们处理的次数 直观上，当我们发现array[i] >= array[i+1]的时候，需要将array[i+1]进行+1操作，使其比前一项大 但 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

递增数组

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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