arrays - 在 O(1) 时间内找到未排序数组的两个索引之间的最大值

Question

在一个未排序的数组中，（我们可以预处理这个数组）。我们如何在 O(1) 时间内回答以下查询？从索引 i 到 j 找到最大值

编辑：预处理可能需要 O(n) 时间和 O(n) 额外内存的顺序，因此经常出现的查询会在 O(1) 时间内得到回答......

Answer 1

没有内存限制或预处理限制？只需制作一个 O(n ²i ) 表，其中包含每个可能的答案（即和的每个可能值对应一个条目j）。这张表可以在 O(n ³ ) 时间内简单地制作，并且可以通过增量计算最大值很容易地降低到 O(n ^{2 )。}

Answer 2

这个问题（称为 Range Minimum Query 问题）得到了解决（O(n) 预处理，O(1) 查询）。来自维基百科：

众所周知，O(n) 时间的预处理足以在 O(1) 时间内回答后续查询。结果方案的空间实际上非常小，即 O(n) 位（参见 Fischer & Heun (2007)）。

RMQ 问题与您的问题完全相同（只需将“最小值”替换为“最大值”）。请参阅http://wcipeg.com/wiki/RMQ#Cartesian_trees以获取算法草图及其正确性和内存/时间保证的证明。

另请参阅此TopCoder 教程，了解可用于解决此问题的不同选项的概述，这些选项基本上是按实现复杂性递增的顺序。

Answer 3

这是不可能的。您将需要遍历数组以找到需要 O(n) 的最大值，或者您需要通过对数组进行排序（比 O(n) 更昂贵）或确定所有可能范围的最大值来预先计算will 比 O(n) 更昂贵，并且需要太多的内存。

Answer 4

除非您的预处理可以大于 O(1)，否则不可能。排序有什么问题？这只是 O(n*log(n)) （如果允许基数排序，则为最大 O(n)）。