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

比如，你来到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)

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

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

第二题咋做？

群里大佬说的：可以先找到一个单增子序列比如[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，就是最后的结果

最大值减最小值就行了吧