找出一个比数组中给定的数字更大的数字

Question

有一个UNSORTED数列:a1,a2,...,an

我们有一个数字，i所以我们有ai

我们想找到数字j，其中j<i和aj>ai像这样:

3,4,9,1,8,10,2,2,6,1
if i=8 then j=6
if i=7, j=6 again
if i=10 then j=9
if i=1 then j=NIL (Not In List)

Answer 1

使用段树可以在O(n)个预处理和O(log n)个查询中完成。

非常简单，每次查询只需O(log^2 n)。首先，建立一个段树，支持在O(log n)上获得段的最大值。其次，对每个查询进行二叉搜索。

I表示max(a_i, ..., a_j) as max(i, j)。假设查询索引是i。如果是max(i+1, n) <= a_i，那么显然没有这样的元素。否则，你必须找到一个最小的j，这样max(i+1, j) > a_i，这是通过对j的二进制搜索来完成的。

为了进一步改进，您必须深入研究段树结构。我会给你们一些基本的概念。假设您必须找到数组中大于x的第一个元素。一开始你在段树的根。如果左子树的最大值是> x，则到左子树，否则到右子树。可以很容易地看到，结束的叶子对应于数组的最左边的元素，即> x。