如何扩充跳表，使我们能够有效地提取跳表中特定片段的最大值？[Skiplist未按值排序]

Question

我有一个我正在努力解决的问题。

我有一个带有元素的跳转列表：element = (date,value)

日期是跳过列表的键，因此，跳过列表是按日期排序的。如何增加跳过列表以使函数Max(d1,d2) -> returns largest value between dates d1 and d2最有效。这些值是整数。

Answer 1

最有效的方法是遍历从d1到d1的每个项目，并选择最大的项目。因为跳过列表是按日期排序的，所以您不能假设任何值的顺序:它们可能是随机排序的。所以你必须看一看每一个。

因此，查找d1的时间为O(log )(平均值:毕竟这是一个跳过列表)，查找最大元素的时间为O(范围)，其中range是介于d1和d2之间(包括这两个值)的项数。

实现这一点的方法是向跳过列表添加一个函数，该函数允许您从任意元素开始迭代列表。几乎可以肯定的是，您已经有一个将按顺序遍历整个列表的函数，所以您所要做的就是创建一个将遍历一系列键(即从开始键到结束键)的函数。