Google Phone 9/30

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

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

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

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;

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

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

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

写一下我的思路

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/

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

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

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

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