01.07 再聊一個算法題吧

題目描述

在一個整數數組中，一個數字減去它左邊的數字得到一個差值，求最大差值的數字。

例如：

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

注意：

只能用右邊的數字減去左邊的數字計算差值。

題目解析

我特別喜歡這道題。因為解決它也不需要太高深的知識，用不到數據結構和高深算法，但是又需要對數據結構和算法有著較好的本質理解。甚至我覺得如果一個沒學過的人看到這個題能有正確的解題思路，說明他對編程有著良好的直覺，可以入門學習了。

下面來一步一步解析。

如果看到這個問題一頭霧水無從下手，不要急，說明你還沒懂解算法題的套路。等套路掌握了就很容易了。

首先，要排除極端情況。如果是面試也一定要問面試者各種極端情況是否需要考慮排除。比如這道題，如果數組只有一個值或者兩個值怎麼辦？

只有一個值那就返回null。兩個值就返回兩者差值。如果面試的時候問一下面試官，還是挺可以加分的。

接下來進入正題。

因為編程的時候，輸入有很多，但是每次我們只能一個一個取。

所以其實思路就是需要建立遊標。如果有學過數據結構就知道里面需要各種遊標做標記。

遊標就是用來逐個取值的。

最初級的想法，我們需要一個變量記錄遇到的最大值，一個變量記錄遇到的最小值，而且要保證遇到的最大值要在最小值的右邊，然後設立一個遊標不斷移動。然後還需要一個變量儲存差值。如果出現更大的差值就取代之。最後輸出這個差值即可，甚至還可以輸出是哪兩個位置的數之差。

好了，思路在這裡了。

這裡可以先轉換一下題目，假設題目不要求只能右邊減去左邊。這個就很簡單，兩次遍歷循環，第一次兩兩比較找到最大值，第二次兩兩比較找到最小值。實際上這個類似排序算法，優化方法也與排序算法類似。

再回到原題，既然要求只能右邊減去左邊，說明換思路。

最繁瑣的就是兩個變量在改變的時候，把它們兩個值對應的索引也記錄並一直保證較小值的索引在較大值索引的左邊。

上面的方法確實繁瑣。有句話說得好，聰明的人是把複雜的事變簡單，這個時候仔細想想，其實保證只能右邊減去左邊，可以有一個最好的辦法就是，用2個變量記錄最大值和最小值，然後遊標逐個移動，碰到了值，如果比最大值大，就更新最大值，比最小值小，就更新最小值。這裡注意需要一個順序問題以避免最大值跑到了最小值的左邊，也就是需要首先判斷這個值比目前存有的最小值要大之後，再和現存的最大值比較。如果比最大值還大，那麼就更新最大值。然後兩者再相減。

那麼解答就可以用python3寫出來了：

<code>importtime 


classSolution(object):
 defmaxDiff(self,arr):
   listlen=len(arr)
   iflistlen<=1:
     print("NaN")
     returnNone
   minnum=min(arr[0],arr[1])
   maxnum=max(arr[0],arr[1])
   maxdiff=arr[1]-arr[0]
   foriinrange(2,listlen):
     ifarr[i]>minnum:
       ifarr[i]>maxnum:
         maxnum=arr[i]
         maxdiff=maxnum-minnum
     else:
       minnum=arr[i]
       maxnum=arr[i]
   # print('minnum:',minnum)
   # print('maxnum:',maxnum)
   # print('maxdiff:',maxdiff)
   returnmaxdiff


if__name__=='__main__':
 solution=Solution()
 arr1= [1]
 arr2= [4,40,-7,5,11,-60,9,0,12]
 solution.maxDiff(arr1)
 start=time.time()
 foriinrange(10000):
   solution.maxDiff(arr2)
 elapsed= (time.time()-start)/10000
 print("elapsed:",elapsed)/<code>

19行 if __name__ == '__main__': 下面的是測試樣例。第5、18、19、20行的print是測試輸出用。

4-6行就是考慮極端情況。

7-9行是初始化，這個題目的數組最起碼得有兩個值，那麼就可以開始初始化，把頭兩個的差值作為目前的最大差值，這二個值裡最小的值作為記錄的最小值，最大的值作為最大值，然後就開始用遊標移動。

如果一個值比最小的值還小，那麼可以更新最小值，這個時候以後用來去減這個最小值的值必須在這個最小值的右側，所以這裡也需要同步跟新一下最大值。然後下一次碰到一個值，如果比目前存的最小值還大，而且比現在存的最大值也大，那麼就可以更新最大值，然後兩者相減。

這樣遊標不斷持續走到終點。

由於數組自己的特點，所以遊標就直接用的是數組的索引。

解法很簡單。

下面再附上一個不設置maxnum的算法：

<code>importtime

classSolution(object):
 defmaxDiff(self,arr):
   listlen=len(arr)
   iflistlen<=1:
     print("NaN")
     returnNone
   minnum=min(arr[0],arr[1])
   maxdiff=arr[1]-arr[0]
   foriinrange(2,listlen):
     ifarr[i]>minnum:
       maxdiff=max(maxdiff,arr[i]-minnum)
     else:
       minnum=arr[i]
   # print('minnum:',minnum)
   # print('maxdiff:',maxdiff)
   returnmaxdiff


if__name__=='__main__': 

 solution=Solution()
 arr1= [1]
 arr2= [4,40,-7,5,11,-60,9,0,12]
 solution.maxDiff(arr1)
 start=time.time()
 foriinrange(10000):
   solution.maxDiff(arr2)
 elapsed= (time.time()-start)/10000
 print("elapsed:",elapsed)/<code>

第二個算法的特點就是不管三七二十一，只更新最小值，只要現在的遊標碰到的值比現在的最小值還大，那我就嘗試用現在遊標碰到的值減去最小值。

所以我增加了time模塊，測試跑一萬次，兩者時間效率上有無差異。

測試的結果是還是第一種方法更搞笑一點點。（註釋掉print是因為它也佔用運行時間）

有興趣的朋友可以自己複製下來運行運行。

我是真的很喜歡這道題。夠簡單又夠有趣。

閱讀更多 火山灰的荷蘭號 的文章

關鍵字: 數據結構 減去 數字