给出了大量array[n]整数作为输入.给出两个指数值 - start,end.希望很快找到 - min & max in the set [start,end](包括)和max in the rest of array(不包括[开始,结束]).
例如-
阵列 - 3 4 2 2 1 3 12 5 7 9 7 10 1 5 2 3 1 1
开始,结束 - 2,7
min,max in [2,7] - 1,12
最多休息 - 10
我想不出比线性更好的东西.但这还不够好,n is of order 10^5而且这种查找操作的数量也是相同的顺序.
任何帮助将受到高度赞赏.
我理解你的问题的方式是你想在一个固定的数组上做一些预处理,然后让你的find max操作非常快.
这个答案描述了一种方法,它执行O(nlogn)预处理工作,然后为每个查询执行O(1)工作.
想法是准备两个2d阵列BIG [a,k]和SMALL [a,k]在哪里
1. BIG[a,k] is the max of the 2^k elements starting at a
2. SMALL[a,k] is the min of the 2^k elements starting at a
您可以通过从k == 0开始以递归方式计算此数组,然后通过将两个先前元素组合在一起来为每个更高元素构建值.
BIG[a,k] = max(BIG[a,k-1] , BIG[a+2^(k-1),k-1])
SMALL[a,k] = min(SMALL[a,k-1] , SMALL[a+2^(k-1),k-1])
然后,您可以通过组合2个预先准备的答案立即找到任何范围的最大值和最小值.
假设您要查找从100到133的元素的最大值.您已经知道最多32个元素100到131(在BIG [100,5]中)以及最多32个元素从102到133(在BIG [102] ,5])所以你可以找到最大的这些来得到答案.
同样的逻辑适用于最小值.您总能找到两个重叠的准备好的答案,这些答案将结合起来为您提供所需的答案.