Google Phone 9/30

这题目如果不提示很难想啊....hard无疑...

WhatsFLAG 发表于 2016-10-2 06:01
所以感觉还是楼主的方法精妙啊，如果不是面试官的提示，感觉好像自己发明了一个算法！感觉楼主的offer已经 ...

我怎么觉得这个题其实挺简单的。
就双指针，一左一右，右指针往左移但是要保持值是不断增大，因为减小没意义，左边就从头找第一个最小的，这样好像还是是o(n2)，明显区间缩小很快。
但是每次左边都从头找明显重复利用了，就建一个最小值数组就不需要从头找就从把之前左指针往右移动找到第一个最小的就可以了。 time o(n) + space o(n)

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

不好意思 TYPO! 第7行应该是nums[i] : smallestSoFar[i - 1]

cheeroh 发表于 2016-10-2 14:27
楼主的第7行应该改成
smallestSoFar = (nums < smallestSoFar) ? nums : smallestSoFar;

谢谢， 是的，我打错字了当时

intaglio 发表于 2016-10-2 13:27
left--是不是应该放在while那层？因为else里面也需要left--？

对的，还发现一个错误。如果left只在if里面 max那里应该改为 max= max>right-left:max:right-left
如果else里面也有left--，max=right-left 就可以了。

补充内容 (2016-10-3 06:06):
max= max>right-left？max:right-left

写一下我的思路

1. int solution2(vector<int> nums) {
   
2.     if (nums.empty()) return 0;
   
3.     vector<int> minvec(nums.size(), nums[0]);
   
4.     for (int i = 0; i < nums.size(); i++)
   
5.         minvec[i] = min(minvec[i - 1], nums[i]);
   
6.     int high = (int)nums.size() - 1, low = high - 1, dis = 0, maxNum = nums[high];
   
7.     for (; low < high && low >= 0; high--) {
   
8.         if (nums[high] < maxNum) continue;
   
9.         while (low > 0 && minvec[low - 1] <= nums[high]) low--;
   
10.         dis = max(dis, high - low);
    
11.         maxNum = nums[high];
    
12.     }
    
13.     return dis;
    
14. }

复制代码

http://www.geeksforgeeks.org/given-an-array-arr-find-the-maximum-j-i-such-that-arrj-arri/

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

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

这个思路真心牛逼！本质上利用了smallestSoFar[i]从右往左一定是非递减的，有点单调栈的思路。如果能想通为什么[2,2,2,2,1,1,1] 返回的是2这题就做出来了

我也是纽约一个白人小哥，在google map 工作的，但是我面的好艰难

LZ这代码好简洁，看上去就是leetcode discuss top里面的答案