再聊一个算法题吧（一个算法可以有几个输入）

题目描述

在一个整数数组中，一个数字减去它左边的数字得到一个差值，求最大差值的数字。

例如：

[4,2,7,5,11,13,9,1]，差值最大为11，是13-2的结果。

注意：

只能用右边的数字减去左边的数字计算差值。

题目解析

我特别喜欢这道题。因为解决它也不需要太高深的知识，用不到数据结构和高深算法，但是又需要对数据结构和算法有着较好的本质理解。甚至我觉得如果一个没学过的人看到这个题能有正确的解题思路，说明他对编程有着良好的直觉，可以入门学习了。

下面来一步一步解析。

如果看到这个问题一头雾水无从下手，不要急，说明你还没懂解算法题的套路。等套路掌握了就很容易了。

首先，要排除极端情况。如果是面试也一定要问面试者各种极端情况是否需要考虑排除。比如这道题，如果数组只有一个值或者两个值怎么办？

只有一个值那就返回null。两个值就返回两者差值。如果面试的时候问一下面试官，还是挺可以加分的。

接下来进入正题。

因为编程的时候，输入有很多，但是每次我们只能一个一个取。

所以其实思路就是需要建立游标。如果有学过数据结构就知道里面需要各种游标做标记。

游标就是用来逐个取值的。

最初级的想法，我们需要一个变量记录遇到的最大值，一个变量记录遇到的最小值，而且要保证遇到的最大值要在最小值的右边，然后设立一个游标不断移动。然后还需要一个变量储存差值。如果出现更大的差值就取代之。最后输出这个差值即可，甚至还可以输出是哪两个位置的数之差。

好了，思路在这里了。

这里可以先转换一下题目，假设题目不要求只能右边减去左边。这个就很简单，两次遍历循环，第一次两两比较找到最大值，第二次两两比较找到最小值。实际上这个类似排序算法，优化方法也与排序算法类似。

再回到原题，既然要求只能右边减去左边，说明换思路。

最繁琐的就是两个变量在改变的时候，把它们两个值对应的索引也记录并一直保证较小值的索引在较大值索引的左边。

上面的方法确实繁琐。有句话说得好，聪明的人是把复杂的事变简单，这个时候仔细想想，其实保证只能右边减去左边，可以有一个最好的办法就是，用2个变量记录最大值和最小值，然后游标逐个移动，碰到了值，如果比最大值大，就更新最大值，比最小值小，就更新最小值。这里注意需要一个顺序问题以避免最大值跑到了最小值的左边，也就是需要首先判断这个值比目前存有的最小值要大之后，再和现存的最大值比较。如果比最大值还大，那么就更新最大值。然后两者再相减。

那么解答就可以用python3写出来了：

?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?=?maxnum?-?minnum
??? ? ? ? ? ?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)

19行 if __name__ == '__main__': 下面的是测试样例。第5、18、19、20行的print是测试输出用。

4-6行就是考虑极端情况。

7-9行是初始化，这个题目的数组最起码得有两个值，那么就可以开始初始化，把头两个的差值作为目前的最大差值，这二个值里最小的值作为记录的最小值，最大的值作为最大值，然后就开始用游标移动。

如果一个值比最小的值还小，那么可以更新最小值，这个时候以后用来去减这个最小值的值必须在这个最小值的右侧，所以这里也需要同步跟新一下最大值。然后下一次碰到一个值，如果比目前存的最小值还大，而且比现在存的最大值也大，那么就可以更新最大值，然后两者相减。

这样游标不断持续走到终点。

由于数组自己的特点，所以游标就直接用的是数组的索引。

解法很简单。

下面再附上一个不设置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])
??? ? ? ?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)

第二个算法的特点就是不管三七二十一，只更新最小值，只要现在的游标碰到的值比现在的最小值还大，那我就尝试用现在游标碰到的值减去最小值。

所以我增加了time模块，测试跑一万次，两者时间效率上有无差异。

测试的结果是还是第一种方法更搞笑一点点。（注释掉print是因为它也占用运行时间）

有兴趣的朋友可以自己复制下来运行运行。

我是真的很喜欢这道题。够简单又够有趣。