我有一个类似于这个1,3,5的数组。对于每一个元素,我需要找到最长的子数组,其中当前元素是最高的。答案是所有子数组的长度之和。
解释一下。
索引-0:元素1 ->最长子数组,元素小于当前元素=1
索引-1:元素3 ->最长子阵,元素小于当前元素= 1,3
索引-2:元素5 ->最长子阵,元素小于当前元素= 1,3,5
最终答案=1+2+3=6个子阵列长度
对于这个问题,我能想出一个蛮力O(N ^ 2)。有没有更好的方法来解决这个问题?
发布于 2020-10-06 03:32:51
我给你两个提示。
提示1:具有时间复杂度和空间复杂度O(n)的解决方案是可能的,n是给定数组Arr中的元素数。dynamic-programming标记使头脑坚持它,而不是探索其他可能的解决方案。
现在就在这里停下来,自己试一试,然后再继续阅读。
。
。
。
。
避免无意中让你读到第二条暗示
。
。
。
。
提示2:使用单调堆栈。
现在就在这里停下来,自己试一试,然后再继续阅读。
我喜欢解决这个问题,谢谢!下面的解决方案是直截了当的,只为堆栈.使用空间。
我将向您展示一个模拟,而不是给出一个规则样式的逐行算法。
Index: 0 1 2 3 4 5
Arr: 44 91 58 54 7 38

上给出的解决方案是否正确?

长度之和= 17,所以,我们有一个正确的解。
后续问题:如果中存在重复的解决方案,会工作吗?如果没有,您将对上述算法进行哪些更改以使其工作?提示:玩>,<,=会有帮助吗?
发布于 2020-10-06 11:25:36
只需在两个方向记录下一大元素的索引,并查找每个元素。O(n)空间和时间
https://stackoverflow.com/questions/64217739
复制相似问题