我想找到某个范围内的最低值。
是每次都要遍历数组还是有什么动态方法?
假设我有输入数组:
index: 0 1 2 3 4 5 6 7
value: 1 4 6 1 6 7 2 3
然后我必须选择 (含)范围内的最小值。例如:
min(0,7) = 1
min(0,2) = 1
min(4,6) = 2
min(1,2) = 4
我对最快的解决方案感兴趣,最好在恒定时间内获得结果。
Array 不会同时改变。
最佳答案
如果您要对同一组数字执行多个查询,那么您需要构造一个 Cartesian Tree .
Cartesian trees may be used as part of an efficient data structure for range minimum queries, a range searching problem involving queries that ask for the minimum value in a contiguous subsequence of the original sequence.
正如文章所说,查询可以在恒定时间内执行。
关于c++ - 范围内的最低值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19756489/