相关疑难解决方法(0)

我想知道,给一个整数列表,比如说l,如果我们被允许从该列表中选择3点的整数,也就是说left,middle,right,其中middle > left, right并left, middle, right出现在列表中的顺序(即index(left)<index(middle)<index(right)),确实存在一个O(n)寻找解决方案最大的middle - left + middle - right？您可能会认为不符合这些条件的列表不会出现(例如[5,0,5],如Eric Duminil所指出的那样)

目前,我能够提出我认为(大致)一个O(n^2)解决方案(如果我错了,请纠正我).

从本质上讲,我目前的想法是:

maximum = 0
for idx in range(1, N - 1):
    left = min(l[0: idx])
    right = min(l[idx + 1:])
    middle = l[idx]

    if left < middle and right < middle:
        new_max = middle - left + middle - right
        maximum = max(new_max, maximum)

帮助/提示将不胜感激.

谢谢!

因此通常使用四个for循环来实现通常且非常低效的最小/最大过滤器.

for( index1 < dy ) { // y loop
    for( index2 < dx ) { // x loop
        for( index3 < StructuringElement.dy() ) { // kernel y
            for( index4 < StructuringElement.dx() ) { // kernel x
                pixel = src(index3+index4);
                val = (pixel > val) ? pixel : val; // max
            }
        }
        dst(index2, index1) = val;
    }
}

然而,这种方法效率很低,因为它再次检查先前检查的值.所以我想知道在下一次迭代中使用先前检查的值来实现这个的方法是什么？

可以对结构元素大小/原点进行任何假设.

更新:我特别渴望了解这种或某种实现的任何见解:http://dl.acm.org/citation.cfm？id = 2114689

我有一个类似的阵列

[5.5, 6.0, 6.0, 6.5, 6.0, 5.5, 5.5, 5.0, 4.5]. 

该数组的所有数字相差0.5,两个连续数字的最大差值也为0.5(它们可以相同;如示例中所示).并且有一个移动间隔或框,其中包含例如3个连续数字,如下所示:

[(5.5, 6.0, 6.0), 6.5, 6.0, 5.5, 5.5, 5.0, 4.5]  # min: 5.5, max: 6.0

并且盒子一个接一个地向右移动:

[5.5, (6.0, 6.0, 6.5), 6.0, 5.5, 5.5, 5.0, 4.5]  # min: 6.0, max: 6.5

[5.5, 6.0, (6.0, 6.5, 6.0), 5.5, 5.5, 5.0, 4.5]  # min: 6.0, max: 6.5

问题是,如何在每个时间框移动时找到框内数字的最小值和最大值？

当盒子和数组的大小像这个例子那样小时,我可以处理它,但我需要将它应用于数组大小100000和盒子大小10000.使用我的方法(我每次使用for循环计算每个max和min盒子通过),花了太多时间(我有100多个阵列要做,需要反复运行).有一些时间限制,所以我需要在0.5秒内像一次计算一样运行它.

给定一个由N个元素组成A[0 .. N - 1]的数组，则产生一个数组B，使得：

 B[i] = min (A[i], A[i+1], ..., A[i+K-1]). 

（数组B将具有完全（N-k + 1）个元素。

时间复杂度应优于O（N * k）

我当时在考虑使用minheap ...但是，heapify会增加复杂性，而且蛮力是O（n * k）

同样，空间复杂度s小于O（k）

这是一个例子

Input: 
A={ 2,1,3,2,5,7,1}, N=7,k=3

Output:
B={1,1,2,2,1}