algorithm - 跳转到下一个最近的元素

Question

给定一个包含 N 个元素的数组，编号从 1 到 N。第 i 个元素的值为 V[i]。此外，所有元素都是不同的。

要从第 i 个元素移动到第 j 个元素，我们需要花费 |i-j| 的成本。但只有在以下情况下，我们才能从第 i 个元素跳到第 j 个元素:

1. j 与键 i 的距离不小于 K 个位置(即 j 不应在 [ i-K+1, i+K-1 ] 范围内)。

2. V[j] < V[i].

每个元素可能有0个或多个可以跳转到的元素。

我们需要找到从每个元素 i 到可以在它之后跳转的最近元素所需的成本总和。如果对于元素 i 没有可以跳转到的下一个元素，则将其成本视为 0。

示例:令 N=5 且 K=1 且数组为 [3,5,4,2,1] 那么这里的答案是 6

解释:

The next jumping elements for:
1 is { }. Closest=none, so cost = 0
2 is { 1 }. Closest=1, so cost = 1
3 is { 1 , 2 }. Closest=2, so cost = 3
4 is { 1 , 2 , 3 }. Closest=2, so cost= 1
5 is { 1 , 2 , 3 , 4 }. Closest=3 or 4, so cost = 1

总成本是6

我知道一个可以在 O(N^2) 中运行的蛮力解决方案。但是 1 <= N <= 2 * 10^5 和 1 <= K,V[i] <= N。那么有什么更好的方法可以解决这个问题？

Answer 1

通过使用二叉树存储索引，您可以将其从 O(n^2) 减少到 O(n^lg(n))。

从空树 T 开始，从 1 -> N 迭代。在每一步中，当你在树中输入新索引时，你也可以得到最接近的索引。