9.26阿里后端笔试第3题，解题思路
题目：
给定一个长度为n的数组{a1,a2,a3,..,an}，定义一个操作：每次选择一个数x，使数组中所有x变成x+1，问至少需要多少次操作，才能得到非降数组
数据范围：
1<=n<=2*10^5;
1<=ai<=10^9
示例：
输入
2，5，3，4，9，7
输出
4
说明：
step 0: 2，5，3，4，9，7
step 1: 2，5，4，4，9，7
step 2: 2，5，5，5，9，7
step 3: 2，5，5，5，9，8
step 4: 2，5，5，5，9，9
思路：
首先想明白一个性质：如果数组已经是（非严格）单调的，那无论怎么操作都不会改变这种单调性。
其次，要保证操作尽可能少，那么就不能有重复操作，比如我们让数组中某个x变成x+1这种操作出现了两次，那肯定有一次是多余的，需要调整操作次序，让一次操作之后，再也不可能出现重复的操作；因此我们尽可能去对数组的最小值操作就行了。
流程：
（1）找到整个数组{a1,a2,a3,..,an}的最小值，如果有多个最小值，找最右边那个，假设是ai；
（2）根据ai位置把原数组划分成左右两个数组{a1,a2,a3,...,ai}和{ai+1,ai+2,...,an}
（3）在左侧数组中，如果它的最大值是max左，那么至少要对ai这个数做（max左 - ai）次操作，让它不断递增，才能让ai的大小不会小于左侧数组的任何一个值，这是左侧数组非降的必要条件
（4）在完成第（3）步的时候实际上导致了左侧数组最小值和最大值都变成了max左 ，它是常数列，已经满足了非降的条件，根据之前提到的性质，左侧数组的单调性已经不会改变了，那我们只需要再来研究右侧数组就好
（5）对右侧数组的处理只需要从第（1）步开始重复上面的操作就行，只是要注意之前第（3）步的操作已经改变了右侧数组的值，原来右侧数组里小于max左的值都变成了max左，其他值保持不变
数据结构：
（i）流程第（1）步要求当前数组的最小值，由于循环过程中，我们不断把数组向右侧“收缩”，那么用一个最小堆来维护数组里的值就行，再用一个hashtable来记录数组中每一个值最右侧的下标位置，这样第（1）步每次的复杂度就是log(n)；
（ii）流程第（3）步要在左侧数组中找最大值，那么在流程之前应该先得到一个“前缀最大值”数组，这样每次只要O(1)的时间就能完成查找，由于第（3）步只会把左侧数组全部变成max左，而max左本身是不变的，所以这个数组不需要去维护；
（iii）在处理完左侧数组，准备处理右侧数组的时候，需要对hashtable[max左]更新，因为现在所有小于max左的值都变成了max左；一边从堆里pop一边更新就行，pop完再判断一下现在最靠右的max左是不是在右侧数组，如果在就把一个max左再放回堆里。
所有的操作数都在第（3）步的（max左 - ai）里，时间复杂度主要来自于堆操作O(nlogn)
类似资料：