我有一个算法问题:
给定一个大小为N的整数数组,找到最大的降幅(不一定连续):max{array[i]-array[j]},其中i>j。
简单的解决方案是使用两个循环遍历所有可能的i和j的值,但时间复杂度为O(n*n)。
我认为改进的解决方案是首先映射数组的索引,对数组进行排序,然后遍历数组以找到最大降幅。这个复杂度是O(nlogn)。
是否有一个线性时间复杂度的解决方案?如何实现?
注:我曾经想过一个线性解决方案:创建两个额外的数组,一个记录从开始到结束的给定数组的最大值,另一个记录从结束到开始的最小值。然后,一次遍历两个数组。但是,有人认为这不正确且占用了太多的空间。因此,我想知道更好的解决方案。 - lijuanliu