我有一个算法问题:
给定大小为N的数组(假设所有元素都是整数),找到最大的drop(不一定是连续的):max {array [i] -array [j]},其约束为:i> j.
简单的解决方案是两个循环并遍历i和j的所有可能值,但时间复杂度为O(n*n).
我认为一个改进的解决方案是首先映射数组的索引,对数组进行排序,然后遍历数组以找到最大的丢弃.这种复杂性是O(nlogn).
有线性时间复杂度的解决方案吗？如何？
PS:我曾经想过一个线性解决方案:创建两个额外的数组,一个是从开始到结束记录给定数组的最大值,另一个是从结尾到开始的最小值.然后,通过两个阵列一通.然而,有人认为不正确并占用太大的空间.所以我想知道一个更好的解决方案. - lijuanliu