范围内的最低值

Question

我想在某个范围内找到最低值.
我每次都要迭代数组还是有动态方法？

可以说我有输入数组:

index: 0 1 2 3 4 5 6 7
value: 1 4 6 1 6 7 2 3

然后我必须选择<a,b>(包括)范围内的最小值.例如:

min(0,7) = 1
min(0,2) = 1
min(4,6) = 2
min(1,2) = 4

我对最快的解决方案感兴趣,最好是在恒定的时间内获得结果.

在此期间不会更改数组.

Answer 1

如果要对同一组数字执行多个查询,则需要构建笛卡尔树.

笛卡尔树可以用作范围最小查询的有效数据结构的一部分,范围搜索问题涉及在原始序列的连续子序列中请求最小值的查询.

正如文章所说,查询可以在恒定的时间内执行.