arrays - 如何在不改变顺序的情况下找到数组中两个数字之间的最小差异，以便它们的差异为正？

Question

根据年份，我得到了以吨为单位的收成。
像 {3,6,12,1,20,25} 。

找出有序年份收获之间收获的最小差异。
对于给定的示例，差异为 2，因为 3 - 1 = 2。保留顺序且结果为正
排序不适用，因为数字已根据年份排序。

一种方法是找到元素之间的所有正差异并选择最小的一个。
但它需要 O(n^2)。

有什么更快的方法吗？
主要任务是在不改变元素顺序的情况下，找到数组中元素之间的最小差异，使它们的差异为正。

Answer 1

根据我对题目的理解，我们需要计算min(a[i] - a[j])在所有有效i之间和 j这样 i < j和 a[i] > a[j] .

您可以从左到右遍历数组并将所有元素保存在支持 insert 的数据结构中和 upper_bound高效操作(例如，C++ 中的 std::set 或 Java 中的 TreeSet)。

伪代码(类似 C++)可能如下所示:

s = empty set
res = INF
for elem in array: // from left to right
     if s.upper_bound(elem) != s.end(): // checks if there is a larger element
          res = min(res, *s.upper_bound(elem) - elem)
     s.insert(elem)

insert 和 upper_bound 操作取 O(log N)时间，所以总的时间复杂度是O(N log N) .