在大小为n的数组的所有大小为L的连续子数组中找到最小值
问题内容:
大小为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];
}
}
有没有比这更好的解决方案了?
问题答案:
您可以使用双头队列(Q)。找到一种方法,使最小的元素始终出现在Q的前面,并且Q的大小永远不会超过L。因此,解决方案总是始终最多插入和删除元素上)。我觉得这足以使您前进。