arrays - 在优于 O(N*M) 的时间内找到数组中多个区间的最小元素

Question

我有三个数组:A、B、C。B 和 C 的对应索引给出了在 A 中搜索的区间。示例:B[0] = 1, C[0] = 7 因此从 A 中的索引 1 到 7(包括)搜索。

我需要找到 A 中每个区间的最小值并将其作为 int 数组返回。我认为我提出的解决方案在 O(N*M) 中运行，其中 N 是数组 A 的大小，M 是 B 和 C 的大小。我遍历 A 中的每个间隔并找到最小值。

有谁知道如何改进 O(N+M) 的解决方案？

注意:网站上说这个问题可以在O(N+M)时间内解决(codility.com)。我不只是猜测。它也来自关于前缀和的部分，但我还没有想出一种方法来使用它们来获得比 O(N*M) 解决方案更好的方法。 A 未排序。

Answer 1

这是 range minimum query 上的一个非常薄的层问题。对于最好的方案，通过 O(N) 的预处理，可以在 O(1) 的时间内回答查询，但实现起来相当复杂。 TopCoder 托管一个 nice tutorial by danielp如果你想试试。