大小为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。因此,解决方案总是始终最多插入和删除元素上)。我觉得这足以使您前进。