计算一个整数数组中最大差值的元素？

Question

面试题， 在一个整数数组中，一个数字减去它左边的数字得到一个差值，求最大差值的数字。如 [4,2,7,5,11,13,9,1]，差值最大为11，是13-2的结果。只能用右边的数字-左边的数字计算差值。

我用php实现的代码，比较暴力，类似于冒泡排序.

$arr = [4,2,7,5,11,13,9,1];
$a = 0;
$b = 0;
for ($i = count($arr) - 1; $i >= 0; $i--) {
    for ($j = 0; $j <= $i - 1; $j++) {
        $tmp = $arr[$i] - $arr[$j];

        if ($tmp > $a) {
            $a = $tmp;
            $b = $arr[$i];
        }
    }
}

echo $b;

求一个更优的算法，语言不限。

Answer 1

@Reming 的算法有一个小漏洞, 如果数据是这样的话, 算出来的实际上是有问题的.

[4, 2, 7, 5, 11, 13, 9, 0, 12]

个人认为, 这个问题有两个关注点:

• 最小值
• 最大差值

但和最大值无关, 我们需要关注的是最大差值, 可能最大值出现的时候, 最小值还没有出现, 而后面出现的数值减去最小值可能反而比较大. 上面的用例就是基于这种逻辑设计出来的.

修改后逻辑为: 向后循环遍历, 记录下到目前为止的最小值 以及 最大差值, 然后计算当前元素-目前为止最小值, 判断大小. 记录最大的差值即可.
基于 @Reming 的代码稍微修改了下:

var arr = [4, 2, 7, 5, 11, 13, 9, 0, 12];
var min = arr[0], maxDValue = 0;

arr.forEach((el, index) => {
  if (min > el) min = el;

  var diff = el - min;
  if (diff > maxDValue) {
    maxDValue = diff;
  };
});

console.log(maxDValue);

再补充一句, 实际上这个问题可以这样想:

• 假设有一个数组[a1, a2, a3, ..., an]

• 那么我们可以分两步计算出来最大差值

  • 计算a1与左边元素的最大差值, a2与左边元素最大的差值, a3与左边元素的最大差值....an与左边元素的最大差值.
  • 计算所有最大差值里的最大值.
• 其中第一步实际上就是就算am(m=1, 2, 3...)与其左边最小值的差值, 所以我们只需要记录当前最小值以及最大的差值即可.

Answer 2

记得 Leetcode 上是买卖股票的题。

O(n)，左往右遍历，只需要维护目前最小的元素以及当前最大差值即可。原理是当遇到比目前记录最小元素更小的元素时，接下来产生的最大差必然是由新的最小元素产生的（因为它更小，差值必然更大）。

function maxDiff (arr) {
  if (arr.length <= 1) {
    return NaN
  }

  let min = Math.min(arr[0], arr[1])
  let maxDiff = arr[1] - arr[0]
  for (let i = 2; i < arr.length; i++) {
    if (arr[i] > min) {
      maxDiff = Math.max(maxDiff, arr[i] - min)
    } else {
      min = arr[i]
    }
  }

  return maxDiff
}

另外也可以从动态规划的角度看

设 g(i) 为 [0..i] 最小的元素，则

g(0) = arr[0]
g(i) = min(g(i-1), arr[i])

设 f(i) 为 [0..i] 最大的差值，则

f(0) = NaN
f(1) = arr[1] - arr[0]
f(i) = max(f(i-1), arr[i]-g(i-1))

Answer 3

[4,2,7,5,11,13,9,1].reduce((result, item, index, data) => Math.max(result, ...[...data].slice(0, index).map(v => item -v)));

[4,2,7,5,11,13,9,1].reduce((result, item, index, data) => Math.max(result, item - Math.min(...[...data].slice(0,index))));

Answer 4

package main

import "fmt"

func main() {
        presort := []int{4, 2, 7, 5, 11, 13, 9, 1}
        length := len(presort)
        min := 0
        maxDiff := 0

        for i := 0; i < length; i++ {
                if presort[i] < min {
                        min = presort[i]
                }
                if presort[i]-min > maxDiff {
                        maxDiff = presort[i] - min
                }
        }
        fmt.Println(maxDiff)
}

Answer 5

import time

class Solution(object):
    def maxDiff(self, arr):
        listlen = len(arr)
        if listlen <= 1:
            print("NaN")
            return None
        minnum = min(arr[0], arr[1])
        maxdiff = arr[1] - arr[0]
        for i in range(2, listlen):
            if arr[i] > minnum:
                maxdiff = max(maxdiff, arr[i]-minnum)
            else:
                minnum = arr[i]
        # print('minnum:',minnum)
        # print('maxdiff:',maxdiff)
        return maxdiff


if __name__ == '__main__':
    solution = Solution()
    arr1 = [1]
    arr2 = [4, 40, -7, 5, 11, -60, 9, 0, 12]
    solution.maxDiff(arr1)
    start = time.time()
    for i in range(10000):
        solution.maxDiff(arr2)
    elapsed = (time.time() - start)/10000
    print("elapsed:", elapsed)

我参考的CRIM写的Python版。我觉得他是思路清晰好懂。

首先排除异常情况，如列表只有1个值的时候。像其他大佬就没考虑这个情况。

然后就是不断更新列表里的最小值和最大差值。

进一步还可以建一个空列表用来记录最终用来计算最大差值的数字在原列表里的位置。

当然，算法还有优化的地方，比如

            if arr[i] > minnum:
                maxdiff = max(maxdiff, arr[i]-minnum)                    

这部分还可以对arr[i]和之前的值比较，除非比之前的大值还大，否则就不用再相差之后再取max。

现在附上优化算法，增加了maxnum用来记录目前的最大值：

import time

class Solution(object):
    def maxDiff(self, arr):
        listlen = len(arr)
        if listlen <= 1:
            print("NaN")
            return None
        minnum = min(arr[0], arr[1])
        maxnum = max(arr[0], arr[1])
        maxdiff = arr[1] - arr[0]
        for i in range(2, listlen):
            if arr[i] > minnum:
                if arr[i] > maxnum:
                    maxnum = arr[i]
                    maxdiff = max((maxnum - minnum), maxdiff)
            else:
                minnum = arr[i]
                maxnum = arr[i]
        # print('minnum:',minnum)
        # print('maxnum:',maxnum)
        # print('maxdiff:',maxdiff)
        return maxdiff


if __name__ == '__main__':
    solution = Solution()
    arr1 = [1]
    arr2 = [4, 40, -7, 5, 11, -60, 9, 0, 12]
    solution.maxDiff(arr1)
    start = time.time()
    for i in range(10000):
        solution.maxDiff(arr2)
    elapsed = (time.time() - start)/10000
    print("elapsed:", elapsed)   

注释掉print是因为这个输出也会占用系统测试时间。
用time测试了一万次，第二种优化后的方法是比第一种高的。

紧接着我有想到，既然都这样了，那都也不用先判断是否比minnum大了，直接和maxnum比就好了。于是代码改成：

import time

class Solution(object):
    def maxDiff(self, arr):
        listlen = len(arr)
        if listlen <= 1:
            print("NaN")
            return None
        minnum = min(arr[0], arr[1])
        maxnum = max(arr[0], arr[1])
        maxdiff = arr[1] - arr[0]
        for i in range(2, listlen):
            if arr[i] > maxnum:
                maxnum = arr[i]
                maxdiff = max((maxnum - minnum), maxdiff)
            else:
                minnum = arr[i]
                maxnum = arr[i]
        # print('minnum:',minnum)
        # print('maxnum:',maxnum)
        # print('maxdiff:',maxdiff)
        return maxdiff


if __name__ == '__main__':
    solution = Solution()
    arr1 = [1]
    arr2 = [4, 40, -7, 5, 11, -60, 9, 0, 12]
    solution.maxDiff(arr1)
    start = time.time()
    for i in range(10000):
        solution.maxDiff(arr2)
    elapsed = (time.time() - start)/10000
    print("elapsed:", elapsed)   

这层优化效果不明显，不过思路就是这样，
目前把这道题我能回答的都回答了。欢迎大家交流。

Answer 6

function getMaxValue(arr) {
    var ret = 0;
    if (Array.isArray(arr)) {
        for (var i = 0; i < arr.length; i++) {
            var num = arr[i];
            var tmp = arr.slice(0, i);
            var min = Math.min.apply(null, tmp);
            if (!Number.isFinite(min)) min = 0;
            if (min < num && num - min > ret) ret = num - min;
        }
    }
    return ret;
}
console.log(getMaxValue([4,2,7,5,11,13,9,1]));