Source: Max Distance

Given an array A of integers, find the maximum of j - i subjected to the constraint of A[i] <= A[j].

If there is no solution possible, return -1.

Example :

A : [3 5 4 2]

Output : 2 
for the pair (3, 4)

解題：

  1. 在不考慮最佳解的情況下，用兩個FOR迴圈窮盡所有組合馬上就可以得到解答，但O(n^2)基本上是保證timeout不可能通過的；
  2. 因此在實際比較時只用一個線性迴圈的情況下必須要先做篩選排序O(nlogn)，問題在於該如何做才能同時符合題目給的兩個條件？
  3. 因題目同時要比較index & value，可採用建立一個標記index之陣列並依照陣列值的大小進行重新排列
  4. 完成排序後，值已從左到右重新排序，故採用線性迴圈時我們只需要跟進index值即可（因右邊值經排序過後必定比左邊值大）。因為目的是求最大的index差距，在迴圈中如果遇到更小的index即可直接更新當前index值，若否則計算目前的index差距是否大於截至目前得到的最大值。

Code:


class Solution:
    # @param A : tuple of integers
    # @return an integer
    def maximumGap(self, A):
        if len(A) == 0: return -1
        arr = []
        # add index info into the array
        for idx, v in enumerate(A):
            arr.append([v, idx])
        arr.sort()
        #[ 5, 3, 11 ] => [[3, 1], [5, 0], [11, 2]]
        cur_idx = arr[0][1]
        max_diff = -1
        for j in arr:
            if j[1]  max_diff:
                    max_diff = j[1] - cur_idx
        return max_diff

GitHub: GitHub

發表留言