寻找最小射程的子阵

Question

给定一个由N个正整数组成的数组，从索引0到N-1，我如何才能找到一个长度为K且范围尽可能小的连续子数组。换句话说，最大（子阵列）-最小（子阵列）是最小化的。如果有多个答案，任何答案都可以。

例如，从[4,1,2,6]中找到最小范围的长度为2的子数组

答案是[1,2]，因为2-1=1给出了所有可能的连续子数组的最小范围。

其他子阵列有[4,1]（范围3），[2,6]（范围4）

我正在使用python，到目前为止，我已经尝试了使用min（）max（）函数进行线性搜索，但这样做似乎效率不高。我想过使用minheap，但我不确定您将如何实现它，我甚至不确定它是否有效。非常感谢任何帮助。

编辑：添加代码

# N = length of array_of_heights, K = subarray length
N, K = map(int, input().split(' '))
array_of_heights = [int(i) for i in input().split(' ')]



min_min = 100000000000000000000

# iterates through all subarrays in the array_of_heights of length K
for i in range(N + 1 - K):
    subarray = land[i : i + K]
    min_min = min(max(subarray)-min(subarray), min_min)

print(min_min)

Answer 1

可以使用numpy来提高执行时间。

例子：

def f1(l,k):
    subs = np.array([l[i:i+k] for i in range(len(l)-k+1)])
    return np.min(subs.max(axis=1) - subs.min(axis=1))

小测试（f2是您在这里的函数）。

>>> arr = np.random.randint(100,size=10000)
>>> timeit.timeit("f1(arr,4)",setup="from __main__ import f1,f2,np,arr",number=1)
0.01172515214420855
>>> timeit.timeit("f2(arr,4)",setup="from __main__ import f1,f2,np,arr",number=1)
14.226237731054425

Answer 2

有一种线性时间算法O（N）用于在指定大小的移动窗口中获得最小值或最大值（而您的实现具有O（N*K）复杂性）

使用collections模块中的deque，您可以实现两个并行deque，为当前窗口位置保持最小值和最大值，并在仅遍历列表后检索最佳差异。

import collections

def mindiff(a, k):
    dqmin = collections.deque()
    dqmax = collections.deque()
    best = 100000000
    for i in range(len(a)):
        if len(dqmin) > 0 and dqmin[0] <= i - k:
            dqmin.popleft()
        while len(dqmin) > 0 and a[dqmin[-1]] > a[i]:
            dqmin.pop()
        dqmin.append(i)
        if len(dqmax) > 0 and dqmax[0] <= i - k:
            dqmax.popleft()
        while len(dqmax) > 0 and a[dqmax[-1]] < a[i]:
            dqmax.pop()
        dqmax.append(i)
        if i >= k - 1:
            best = min(best, a[dqmax[0]]-a[dqmin[0]])
    return best

print(mindiff([4, 1, 2, 6], 2))