10/14 Google onsite 面经

LZ第四轮第二题可以用Deque吧？复杂度O(N)比heap好点

还来得及吗 发表于 2014-10-21 11:38
LZ第四轮第二题可以用Deque吧？复杂度O(N)比heap好点

我觉得楼主的方法可能已经是最好的了。你用deque的话，如果pop掉当前范围唯一的最小数的话，你怎么确定下一个最小数？

kuyen 发表于 2014-10-21 12:50
我觉得楼主的方法可能已经是最好的了。你用deque的话，如果pop掉当前范围唯一的最小数的话，你怎么确定下 ...

我想的用是两个deque，一个存最大，一个存最小，每次求diff然后和max比较，应该是O(N)吧？

还来得及吗 发表于 2014-10-21 23:38
我想的用是两个deque，一个存最大，一个存最小，每次求diff然后和max比较，应该是O(N)吧？

赞，这确实是O(N)的方法
维护2个单调队列，每次尝试更新头尾，取出两个队列的头，相减后与max比较即可。

第一题是什么思路啊

还来得及吗 发表于 2014-10-21 23:38
我想的用是两个deque，一个存最大，一个存最小，每次求diff然后和max比较，应该是O(N)吧？

可以说的再具体点吗？我在想这个方法可以处理重复数字吗？

kuyen 发表于 2014-10-22 01:22
可以说的再具体点吗？我在想这个方法可以处理重复数字吗？

http://leetcode.com/2011/01/sliding-window-maximum.html
重复是可以的吧。。感觉这个问题就是sliding window max的变型，不过是用两个分别记录最大最小。

还来得及吗 发表于 2014-10-22 08:01
http://leetcode.com/2011/01/sliding-window-maximum.html
重复是可以的吧。。感觉这个问题就是sliding ...

谢谢啊。解释的很清楚

第二轮的题目是什么意思 没太懂。。