Google Phone 9/30

所以感觉还是楼主的方法精妙啊，如果不是面试官的提示，感觉好像自己发明了一个算法！感觉楼主的offer已经在路上了，膜拜一下

不好意思 下午出去了 回家找了找昨天的草纸  把代码贴出来分享一下

是根据我那个思路写的，如果不对还请大牛们指出!

1. public int findMaximumGap(int[] nums){
   
2.         // Invalid
   
3.         if (nums == null || nums.length == 0) return 0;
   
4.         int[] smallestSoFar = new int[nums.length];
   
5.         smallestSoFar[0] = nums[0];
   
6.         for (int i = 1; i < nums.length; ++i) {
   
7.             smallestSoFar[i] = (nums[i] < smallestSoFar[i - 1]) ? nums[i] : smallestSoFar[nums.length - 1];
   
8.         }
   
9.         int max = 0;
   
10.         for (int j = nums.length - 1; j > max; j--){
    
11.             while ((j > max) && (nums[j] >= smallestSoFar[j - max - 1])) {
    
12.                 ++max;
    
13.             }
    
14.         }
    
15.         return max;
    
16.     }

复制代码

补充内容 (2016-10-3 03:59):
SorrY 各位，有一处TYPO 第七行最右边的坐标应该是i 不是nums.length-1，打上来的时候打错了 抱歉

木易wen 发表于 2016-10-2 04:06
lz能上一下代码么？只想到了O(nlgn)解法， 想看一下你怎么做的，谢谢

HI 已经贴上来啦

Hualiang 发表于 2016-10-2 02:27
第二题不是buy and sell stock吗？

不是啊，这是max(j-i),不是A[j]-A[i]

lz解法才是对的。

ericlee27 发表于 2016-10-2 06:57
不好意思 下午出去了 回家找了找昨天的草纸  把代码贴出来分享一下

是根据我那个思路写的，如果不对还请 ...

1.         public static int maxDistance(int[] A) {
   
2.                 if(A.length<2)
   
3.                         return 0;
   
4.                 int[] smallest = new int[A.length];
   
5.                 int min = Integer.MAX_VALUE;
   
6.                 for (int i = 0; i < A.length; i++) {
   
7.                         min = A[i] > min ? min : A[i];
   
8.                         smallest[i] = min;
   
9.                 }
   
10.                 // left从right左边一位开始逐渐左移
    
11.                 int right = A.length - 1, left = right - 1;
    
12.                 int max = 0;
    
13.                 while (right >= max&&left>=0) {
    
14.                         if (A[right] > smallest[left]) {
    
15.                                 max = right - left;
    
16.                                 left--;
    
17.                         } else {
    
18.                                 right--;
    
19.                         }
    
20.                 }
    
21.                 return max;
    
22.         }

复制代码

一样解法

gaohannk 发表于 2016-10-2 12:26
一样解法

left--是不是应该放在while那层？因为else里面也需要left--？

ericlee27 发表于 2016-10-2 06:57
不好意思 下午出去了 回家找了找昨天的草纸  把代码贴出来分享一下

是根据我那个思路写的，如果不对还请 ...

lz我怎么感觉你的代码跑｛8，8，6，6，6，1，7，2，4｝这个test case不太对呀。。

gbwta 发表于 2016-10-2 14:08
lz我怎么感觉你的代码跑｛8，8，6，6，6，1，7，2，4｝这个test case不太对呀。。

楼主的第7行应该改成
smallestSoFar[i] = (nums[i] < smallestSoFar[i - 1]) ? nums[i] : smallestSoFar[i - 1];

ericlee27 发表于 2016-10-2 06:57
不好意思 下午出去了 回家找了找昨天的草纸  把代码贴出来分享一下

是根据我那个思路写的，如果不对还请 ...

Nice! 祝lz大神onsite顺利