java - 是否可以重写代码使时间复杂度为 O(nlogn)？

Question

我想找出数组中两个数字之间的最大差值，被减数必须在减法器之前。例如:在一个数组(3,1,5,4,2)中，最大差应该是3(5-2)。在数组(100, 3 ,200)中，最大差应该是97(100-3)。

int max = 0, diff;
for(int i = 0; i<n; i++){
  for(int j = i+1; j < n; j++){
    diff = D[i] - D[j];
    if(diff > max)
      max = diff;
  }
}
return max;

我知道它的时间复杂度为 O(n^2) 但我希望它正好是 O(nlogn)。

Answer 1

从最后一个元素到第一个元素遍历数组。

维护两个变量 answer 和 mintillnow。

For each element i:

    answer=max(answer,i-mintillnow)    

    mintillnow=min(mintillnow,i)

最终答案可以在遍历结束时的answer中找到。

时间复杂度:- O(n)

---

如果出于某种原因你希望它正好是 O(log(n)):-

维护一个最小堆和一个答案变量。

在每一步，

查询最小堆中的最小元素，然后从当前元素中减去它，并检查它是否大于答案变量。

将当前元素压入最小堆。

插入最小堆需要 O(log(n))

查询最小值需要 O(1)。

总时间复杂度:- O(n log(n))