arrays - 算法 - 最小大于大小

Question

我有一个问题:

我们有一个整数数组(大小为 n)[x_1,x_2,...,x_n]

我们必须找到最长的公共(public)部分 [x_i,x_i+1,...,x_j] (x_i,x_i+1,...,x_j) 的最小值>= j-i+1 f.e [2,2,1,4,3,3,1] -> 3(最长的正确部分是4,3, 3)

我不知道如何将时间减少到 O(n^2) 以下(检查每个片段)我的第二个想法是:每个值 x_k 都等于该部分可能具有的“长度范围”，如果数字较小，则我们更改“长度范围”(同时计算这有多长段)，但我不知道如果我们得到更多的数字该怎么办

(我真的很感谢任何帮助 - 可能还有另一个更简单的解决方案，但我没有看到)

Answer 1

Caterpillar 方法，O(n)，假设所有整数都是正数:

• 将左右指针放在第一个数字上，你的最小值 = 这个数字。长度 = 1
• 将右指针前进一位，检查条件(你很容易知道是否有新的最小值，并且你知道长度 += 1)
• 如果您不能在不破坏条件的情况下推进右指针，则推进左指针并更新您的值
• 如果左指针也不能前进，则说明找到了满足条件的节。注意它的长度，并在下一个索引上以同样的方式开始一个新的部分。

给你的例子:

[2,2,1,4,3,3,1]
[2] <- The first 2
[2,2] <- Moved the right
[2] <- Moved the left, both R and L are pointing at the second 2
<-Can't move either, note max length and indices from previous run.
[1] <- Starting again
<-Can't move either
[4] <- Starting again
[4,3] <- Right
[4,3,3] <- Right (New max length and indices noted)
[3,3] <- Left. Doesn't improve the max
[3] <- Left again.
<- Can't move either, note max and indices, in this case overwrite length
[1] <-Start again
<- end of loop, check global max length, output

这是 O(n)，因为每个指针(L 和 R)仅在任何给定索引上移动一次。

我认为这应该足以让您用您选择的任何语言编写算法。注意循环结束条件，因为如果数组用完，您必须检查全局最大长度。