请问今天阿里后端笔试的第三题咋做

第三题是：

给定一个长度n的数组，每次可以选择一个数x 让这个数组中所有的x都变成x+1，问你最少的操作次数，使得这个数组变成一个非降数组

输入：n 代表数组长度；数组信息

数据量 n <= 3 * 10^5 ？（不确定）, 每一个数据长度 ai <= 10^9

输出：最小操作次数

例如

输入:[2, 5, 3, 4, 9, 7]

输出:4

3 => 4 [2, 5, 4, 4, 9, 7]

4 => 5 [2, 5, 5, 5, 9, 7]

7 => 8 => 9 [2, 5, 5, 5, 9, 9]

一共四次

不会做求思路

#阿里笔试#

全部评论

推荐最新楼层

左程云

University of Chicago Java

比如，你来到8，已知8的右边最小值是5，如下 …8…5… 你就知道，5这个数是一定要增长到8才行的。5 -> 8，增长3次。我们用线段树，5…7范围上，都设置成1！注意！不是+1，是线段树里update操作！不是add操作！表示：所有的5肯定都要变的(线段树里5位置+1，表示关于5要操作一次) 所有的6肯定都要变的(线段树里6位置+1，表示关于6要操作一次) 所有的7肯定都要变的(线段树里7位置+1，表示关于7要操作一次) 然后，假设你接下来，来到7，7的右边最小值还是5，如下： …8 7…5… 我们用线段树，5…6范围上，都设置成1！你会发现，其实没啥变化，因为之前5…7范围都已经设置成1了。这正好是我们要的效果！然后，假设你接下来，来到9，9的右边最小值还是5，如下： …8 7 9…5… 我们用线段树，5…8范围上，都设置成1！你会发现，其实只在8位置上变化了，因为之前5…7范围上，都已经设置成1了。最后你看看线段树里，总体累加和是多少就可以了。再举个例子： 13 6 30 19 你来到13，发现右边最小值是6，于是线段树6…12范围，都设置成1 你来到6，发现右边最小值>=6，于是线段树什么也不做。你来到30，发现右边最小值是19，于是线段树19…29范围，都设置成1 你来到19，线段树什么也不做。最终，线段树里，只有6…12、19…29范围上有1，所以线段树整体累加和是18。就是我们要的答案。因为值在10^9范围，所以用开点线段树，或者，用线段树离散化处理。都可以。最小值这个信息可以用预处理数组。时间复杂度O(N * log N)

1 回复分享

发布于 2022-09-27 10:28 四川

kylinnnnn

浙江大学 C++

我写了一个，可以看下，可惜考试的答的很烂

1 回复分享

发布于 2022-09-27 00:10 浙江

勇敢牛牛必拿offer

东北林业大学 C++

同学同花顺尝试一下吗，面试简单不造火箭，可保姆式全程跟进度，我帖子有内推

点赞回复分享

发布于 2022-09-27 09:34 浙江

要毕业喽

复旦大学 C++

第二题咋做？

点赞回复分享

发布于 2022-09-27 08:49 上海

牛客7206334号

楼主

门头沟学院自然语言处理

群里大佬说的：可以先找到一个单增子序列比如[2, 5, 3, 4, 9, 7] 就可以找到[2, 5, 9] 然后每一个都可以看做一个子区间的最大值，比如 2是[2]的最大值，5是[5, 3, 4]的最大值，9是[9, 7]的最大值，并获得这样的每个子区间的最小值，就可以得到多个闭区间 [最小值, 最大值]，比如这里就可以得到[2, 2] [3, 5] [7, 9] 合并这些区间，（这个样例不用合并），合并后得到每个区间长度的和，比如这里就是5 -3 + 9 - 7 = 4，就是最后的结果

点赞回复分享

发布于 2022-09-26 23:47 北京

ElliotChan201903030311475

中国科学技术大学 C++

最大值减最小值就行了吧

点赞回复分享

发布于 2022-09-26 23:41 江苏