优化“找到最大的差异”挑战。

我面临着要用JavaScript解决的代码挑战,事实证明这是您不仅需要解决它,还需要很好地解决它的一种。

尊重。

面临的挑战是,给您输入了一个数字数组,并且需要在数组中索引为i和j的两个项目之间找到最大的正差。 条件是j nums [j]。 例如,如果nums = [4,5,3,5,7,8,1],其中i = 4并且j = 2,则您有7 – 3 =4。但是,最大值出现在i = 5和j = 2,nums [i] = 8,nums [j] = 3,相差5。

解决暴力问题的一个简单问题是:

这将产生O(n²)时间解,因为它是一个双重嵌套循环。 对于较小的输入数组,它可以很好地工作,但是挑战尤其是喂入了几个大小大于100,000 in的数组。因此,效率是关键。

我意识到,对于i的每个值(最外面的循环),都有一种方法可以立即确定是否有可能找到一个新的最大值。 本质上,对于i的每个值,您还应跟踪直到该点为止的最低值。 称之为smallestNum。 然后,对于该i值,在进入第二个循环之前,确定nums [i] -smallestNum是否小于当前的greatDiff。 如果是这样,则意味着nums [j]的值i可能没有值,该值可能会产生大于estimateDiff的值,因此您将继续进行下一个迭代。

对于每个i,我认为这是O(n log n)时间,无论您是否陷入嵌套循环都取决于在运行时评估的某些条件。

(由于基准测试很常见,因此我还忽略了一些计时功能。)