在一个数组中，找到一个优化的算法，用于查找最长子数组的长度之和，当前元素是子数组中最高的
In an array, find an optimized algorithm for finding sum of lengths of longest subarray with current element being the highest in the subarray
我有一个类似于 [1,3,5] 的数组。对于这些元素中的每一个，我都需要找到当前元素最高的最长子数组。答案将是所有子数组的长度之和。
说明。
index - 0 : 元素 1 -> 元素小于当前元素的最长子数组 = [1]
index - 1 : 元素 3 -> 元素小于当前元素的最长子数组 = [1,3]
index - 2 : 元素 5 -> 元素小于当前元素的最长子数组 = [1,3,5]
最终答案 = 1 + 2 + 3 = 6 [单个子数组的长度]
我能够想出一个 O(N ^ 2) 的蛮力来解决这个问题。有没有更好的办法解决这个问题？
我给你2个提示。
提示1：时间复杂度和Space复杂度O(n)的解决方案是可能的。n是元素的数量给定数组 Arr。 dynamic-programming 标签使头脑坚持它而不是探索其他可能的解决方案。
现在就到此为止，在进一步阅读之前亲自尝试一下。
.
.
.
.
故意留空以避免让你无意中读到第二个提示
.
.
.
.
提示 2： 使用单调堆栈。
现在就到此为止，在进一步阅读之前亲自尝试一下。
我喜欢解决这个问题，谢谢！ 下面的解决方案是直接一次传递并且只使用space用于堆栈。
我不给出常规风格的 line-by-line 算法，而是向您展示一个模拟。
Index: 0 1 2 3 4 5
Arr: 44 91 58 54 7 38
上面给出的解是否正确？
长度之和=17。所以，我们有一个正确的解决方案。
Follow-up 问题：
如果 Arr 中存在重复项，上述解决方案是否有效？如果不是，您将对上述算法进行哪些更改以使其工作？提示：玩弄 >、<、= 会有帮助吗？
只要记录next greater element的两个方向的索引，每个元素查找即可。 O(n) space 和时间。
我有一个类似于 [1,3,5] 的数组。对于这些元素中的每一个，我都需要找到当前元素最高的最长子数组。答案将是所有子数组的长度之和。
说明。
index - 0 : 元素 1 -> 元素小于当前元素的最长子数组 = [1]
index - 1 : 元素 3 -> 元素小于当前元素的最长子数组 = [1,3]
index - 2 : 元素 5 -> 元素小于当前元素的最长子数组 = [1,3,5]
最终答案 = 1 + 2 + 3 = 6 [单个子数组的长度]
我能够想出一个 O(N ^ 2) 的蛮力来解决这个问题。有没有更好的办法解决这个问题？
我给你2个提示。
提示1：时间复杂度和Space复杂度O(n)的解决方案是可能的。n是元素的数量给定数组 Arr。 dynamic-programming 标签使头脑坚持它而不是探索其他可能的解决方案。
现在就到此为止，在进一步阅读之前亲自尝试一下。
.
.
.
.
故意留空以避免让你无意中读到第二个提示
.
.
.
.
提示 2： 使用单调堆栈。
现在就到此为止，在进一步阅读之前亲自尝试一下。
我喜欢解决这个问题，谢谢！ 下面的解决方案是直接一次传递并且只使用space用于堆栈。
我不给出常规风格的 line-by-line 算法，而是向您展示一个模拟。
Index: 0 1 2 3 4 5
Arr: 44 91 58 54 7 38
上面给出的解是否正确？
长度之和=17。所以，我们有一个正确的解决方案。
Follow-up 问题：
如果 Arr 中存在重复项，上述解决方案是否有效？如果不是，您将对上述算法进行哪些更改以使其工作？提示：玩弄 >、<、= 会有帮助吗？
只要记录next greater element的两个方向的索引，每个元素查找即可。 O(n) space 和时间。