我有一个大小为 1 的数组 A(0 索引)。
我想找到数组 A 中索引 k1 (k1>=0) 和 A.size()-1（即最后一个元素）之间的最小值。
然后我会在数组末尾插入值：（给定范围内的最小元素+一些“随机”常量）。然后我有另一个查询来查找索引 k2 和 A.size()-1 之间的最小值。我发现，在末尾插入值：（给定范围内的最小值+另一个“随机”常量）。我必须做很多这样的询问。
假设我有 N 个查询。朴素的方法需要 O(N^2)。
不能使用线段树，因为数组不是静态的。但是，一个聪明的方法是为大小为 N+1 的数组创建线段树；事先并用无穷大填充未知值。这会给我 O(Nlog N) 复杂度。
还有其他方法可以实现 NlogN 复杂度甚至 N 吗？
这里完全没有必要使用树这样的高级数据结构。只需一个简单的局部变量和列表就可以完成这一切：
创建一个空列表（例如minList).
从end索引并转到start的索引最初给出的数组，放入最小值（直到该索引end）在列表的前面（即做push_front).
假设提供的数组是：
70 10 50 40 60 90 20 30
所以得到的结果是minList将：
10 10 20 20 20 20 20 30
这样做之后，你only需要跟踪其中的最小值新追加的连续修改数组中的元素（例如，minElemAppended).
假设你得到k = 5 and randomConstant= -10，那么
minElemAppended = minimum(minList[k-1] + randomConstant, minElemAppended)
通过采用这种方法，
- 您不需要遍历附加部分，甚至不需要遍历初始给定数组。
- 您可以选择根本不附加元素。
- 时间复杂度：
O(N)处理N查询。
- 空间复杂度：
O(N)来存储minList
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
