Google Phone 9/30

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

lz能上一下代码么？只想到了O(nlgn)解法， 想看一下你怎么做的，谢谢

不好意思，刷屏了，刚又试了一下双指针的做法，貌似也是正确的，时间O(n),不用空间

1. public int maxDistance3(int[] A) {
   
2.         if(A.length < 2) {
   
3.             return 0;
   
4.         }
   
5.         int max = 0;
   
6. 
   
7.         int left = 0, right = A.length - 1;
   
8.         while (left < right) {
   
9.             if (A[left] <= A[right]) {
   
10.                 max = Math.max(max, right-left);
    
11.                 right--;
    
12.             } else {
    
13.                 left++;
    
14.             }
    
15.         }
    
16. 
    
17.         return max;
    
18.     }

复制代码

test cases:

1. 
   
2. []
   
3. [1, 10, 6]
   
4. [1, 10, 6, 3, 2, 3, 4, 5, 6]
   
5. [6, 1, 10, 6, 3, 2, 3, 4, 5, 6]
   
6. [100, 6, 1, 10, 6, 3, 2, 3, 4, 5, 6]
   

复制代码

跑步去鸟。。。。

rcholic 发表于 2016-10-2 03:52
用dynamic programming的思路写了一个，测试结果正确，但是空间O(n), 时间复杂度貌似是O(n^2)了:( ...

n2就不用dp了。。直接全扫一遍找最大

木易wen 发表于 2016-10-2 04:10
n2就不用dp了。。直接全扫一遍找最大

我晚上回家贴哈

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

rcholic 发表于 2016-10-2 04:06
不好意思，刷屏了，刚又试了一下双指针的做法，貌似也是正确的，时间O(n),不用空间

看了代码还是不敢苟同啊，比如2，3，1？

yhl 发表于 2016-10-2 03:50
试试看对吗？．．

int maxGap(vector nums)

[2, 1, 4, 5, 3, 0, 6, 7, 1, 1]这个不对，应该是8

WhatsFLAG 发表于 2016-10-2 04:21
看了代码还是不敢苟同啊，比如2，3，1？

［2，3，1], yeah you got me