arrays - 范围查询：数组 A 中索引范围 [l : r] 中存在的大于 X 且小于 Y 的最大元素

Question

你得到一个正整数数组 A 和一些查询。

在每个查询中，都会给您正整数 X、Y、l 和 r。

对于每个查询，您要在数组 A 的 [l : r] 范围内找到大于 X 且小于 Y 的最大元素。如果不存在这样的元素，则输出 -1。

我有一个类似问题的解释，你要在一个数组范围内找到小于 K 的最大元素。但是在这里我无法应用该逻辑。

预期时间是 O(log n) 或多对数时间。

Answer 1

你需要一个堆数据结构。但是我一直注意到使用波浪号而不是大 O 的时间复杂性。因此，具有 N 项的堆数据结构不会超过 ~1 + logN 比较和删除 ~2logN，如果你使用大 O，那么它相当于 O(日志 N) 。

Answer 2

I had an explanation of similar question where you are to find the maximum element less than K in a range of array. But here I am not able to apply that logic.

我不知道你的解释。但我认为你可以在此基础上再接再厉。

假设您应用该逻辑并发现最大元素小于Y。设最大元素为u (-1 if no such value)。

if (u > X)
{
    return u;
}
else
{
    return -1;
}