查找大小为n的数组的大小l所有连续的子阵列的最小数量 [英] Find the min number in all contiguous subarrays of size l of a array of size n

问题描述

在大小李的一个子的最小数目必须找到它的所有子数组的数组中。有没有比扫描通过任何其他方式，所有的子阵的独立。

The minimum number in a subarray of size L.I have to find it for all the subarray's of the array. Is there any other way than scanning through all the subarray's individually.

我心里有一个解决方案。

I have one solution in mind .

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];
    }
}

有没有比这更好的SLOUTION。

Is there any better sloution than this.

推荐答案

您可以使用双端队列（Q）.Find的方式，使得最小的元素总是出现在Q的前部和Q的大小就超过L.因此，你总是在插入和删除元素最多一次使该解决方案为O（n）。我觉得这是足够的暗示，让你去。

You can use a double ended queue(Q) .Find a way such that the smallest element always appears at the front of the Q and the size of Q never exceeds L. Thus you are always inserting and deleting elements at most once making the solution O(n). I feel this is enough hint to get you going.

这篇关于查找大小为n的数组的大小l所有连续的子阵列的最小数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！