Google Phone 9/30

试试看对吗？．．

int maxGap(vector<int> nums)
{
   vector<int> min(nums.size(), INT_MAX);
   int minIndex = 0, maxGap = 0;

   for (int i = 0; i < nums.size(); i++)
   {
      if (nums[i] <= nums[minIndex])
      {
         minIndex = i;
      }
      min[i] = minIndex;
   }

   int r = nums.size() - 1;

   while (r >= 0)
   {
      int tmp = r;

      while (tmp > 0 && nums[r] > nums[min[tmp]])
      {
         maxGap = max(maxGap, r - min[tmp] + 1);
         tmp = min[tmp] - 1;
      }

      if (r == tmp)
         break;

      r = tmp;
   }

   return maxGap;
}

用dynamic programming的思路写了一个，测试结果正确，但是空间O(n), 时间复杂度貌似是O(n^2)了:(

1. public int maxDistance2(int[] A) {
   
2.         if(A.length < 2) {
   
3.             return 0;
   
4.         }
   
5. 
   
6.         int n = A.length;
   
7.         int[] dp = new int[n];
   
8.         dp[0] = 0;
   
9.         for (int i = 1; i < n; i++) {
   
10.             int curMinIndex = minIndex(A, i);// < i ? 1 : 0; // TODO: this is not working yet
    
11.             dp[i] = Math.max(dp[i-1], curMinIndex);
    
12.         }
    
13. 
    
14.         System.out.println(Arrays.toString(dp));
    
15. 
    
16.         return dp[n-1];
    
17.     }
    
18. 
    
19.     // find the minimum index where nums[i] <= nums[curPos]
    
20.     private int minIndex(int[] nums, int curPos) {
    
21.         int result = curPos;
    
22.         int k = curPos-1;
    
23.         while (k >= 0) {
    
24.             if (nums[k] <= nums[curPos]) {
    
25.                 result = k;
    
26.             }
    
27.             k--;
    
28.         }
    
29. 
    
30.         return curPos - result;
    
31.     }

复制代码

补充内容 (2016-10-2 03:55):
// find the minimum index where nums[i] <= nums[curPos]
应该改为
// find the max distance between the current position and the element that satisfies A[i] <= A[curPos]

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了。。直接全扫一遍找最大

我晚上回家贴哈

其实这个题可以转化成一个这样的题目：
假设你的数组是： A =［10, 2, 6, 1, 4, 5, 6］

将这个数组做成prefix diff: D = A[i] - A[i-1] (for i > 0), 转化成这个 D = [0, -8, 4, -5, 3, 1, 1]

题目相当于问在D数组中找出sum为0的区间长度，上面加粗体的部分即为答案！和best time to buy and sell stocks那个题差不多，只不过是问法变了

补充内容 (2016-10-2 04:20):
更正：D = A[i] - A[i-1] (for i > 0)

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