假设我有一个列表:
L = [2,5,1,8,3,7,9,4,6,10]
或类似的东西
而且我希望能够创建一个二维列表/数组/等来描述所有可能范围的最小值(例如，最小值[0][3] 表示查看元素 0 到 3 时的最小值)。
例如:
Range(0 through 3) = minimum is 1
Range(5 through 5) = minimum is 7
Range(3 through 8) = minimum is 3
等等，对于所有可能的范围。有没有比 n^2 次更好的方法？
最佳答案
为它建立一个线段树。查询时间为 O(logn)。 http://en.wikipedia.org/wiki/Segment_tree
关于在列表中查找所有可能子范围的最小值的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9676494/