Max Distance

这是一道GG电面题。
1.题意：给一个Unsorted array A，for all A[i] <= A[j]，求j-i的最大值。O(N) time, O(N) space.
http://www.geeksforgeeks.org/given-an-array-arr-find-the-maximum-j-i-such-that-arrj-arri/
2.算法：

这个题最简单的事O(N^2)解法，假设扫到index为j那个点的时候，最大distance为max在A[j]点找最小的i使得A[i] <= A[j]，这个i点从j-max-1开始。

HINT：Space是O(N)，可以用一个array存smallest so far

不能按照之前的思路走，因为之前的思路如果额外加一个smallest so far 的array并没有帮助，A[j]并不知道i是谁。

O(N)time 考虑two pointer。

用A[j]和smallest[j-max-1]比较

A[j]  >= smallest[j-max-1] 更新max=max+1
A[j]  < smallest[j-max-1] j--
j>j-max-1, j-max-1>=0 => j>=max+1
因此O(N)

 public int maxDistance(int[] nums){  
   int[] smallest = new int[nums.length];  
   int min = Integer.MAX_VALUE;  
   for(int i = 0; i < nums.length; i++){  
     if(nums[i] < min){  
       min = smallest[i];  
     }  
     smallest[i] = min;  
   }  
   int j = nums.length-1;  
   int max = 0;  
   while(j >=max+1){  
     while(nums[j] >= smallest[j-max-1]) max++;  
     j--;  
   }  
   return max;  
 }