一尘不染

在大小为n的数组的所有大小为L的连续子数组中找到最小值

algorithm

大小为L的子数组中的最小数目。我必须为该数组的所有子数组都找到它。除了单独扫描所有子阵列之外,还有其他方法吗?

我有一个解决方案:

a[n]//the array
minimum[n-l+1]//the array to store the minimum numbers

minpos=position_minimum_in_subarray(a,0,l-1);
minimum[0]=a[minpos];
for(i=1;i<=n-l-1;i++)
{
    if(minpos=i-1)
    {
        minpos=position_minimum_in_subarray(a,i,i+l-1);
    }
    else {
        if(a[minpos]>a[i+l-1]) minpos=i+l-1;
        minimum=a[minpos];
    }
}

有没有比这更好的解决方案了?


阅读 228

收藏
2020-07-28

共1个答案

一尘不染

您可以使用双头队列(Q)。找到一种方法,使最小的元素始终出现在Q的前面,并且Q的大小永远不会超过L。因此,解决方案总是始终最多插入和删除元素上)。我觉得这足以使您前进。

2020-07-28