大意了，尼玛 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

大意了，尼玛

大意了，尼玛# JobHunting - 待字闺中

p*u2013-12-12 08:12

1 楼

sliding window那个题，rocket fuel的烙印不让用STL，非要手写heap，还要求删除任
意元素的复杂度也是O(logn)
一般不都是鼓励用库的么！g家onsite有个稍麻烦点但是最后也用heap的题，用STL面试
官就很满意啊。。。
更新下题目：
You are given an array of size n. There is a sliding window of size k(Return an array containing max element in each window position(from leftmost
window position to rightmost).
Eg.
input: A=4,7,3,6,8,2,4,3,2,5,4 k=4
output:B=7,8,8,8,8,4,5,5

c*m2013-12-12 08:12

2 楼

sliding window哪到题需要用heap（不是deque）？能详细说一下吗？谢谢

p*u2013-12-12 08:12

3 楼

原帖已更新

【在 c****m 的大作中提到】

: sliding window哪到题需要用heap（不是deque）？能详细说一下吗？谢谢

b*c2013-12-12 08:12

4 楼

sliding max?
no heap, use deque

l*62013-12-12 08:12

5 楼

It would be better if you use two max stack to solve this problem

b*c2013-12-12 08:12

6 楼

leetcode.com

w*s2013-12-12 08:12

7 楼

这个是amortized O(n)的算法，所以不需要用heap，不过老印不让用STL也挺奇怪的
解答leetcode上有：http://leetcode.com/2011/01/sliding-window-maximum.html

leftmost

【在 p*u 的大作中提到】

: sliding window那个题，rocket fuel的烙印不让用STL，非要手写heap，还要求删除任
: 意元素的复杂度也是O(logn)
: 一般不都是鼓励用库的么！g家onsite有个稍麻烦点但是最后也用heap的题，用STL面试
: 官就很满意啊。。。
: 更新下题目：
: You are given an array of size n. There is a sliding window of size k(: Return an array containing max element in each window position(from leftmost
: window position to rightmost).
: Eg.
: input: A=4,7,3,6,8,2,4,3,2,5,4 k=4

p*u2013-12-12 08:12

8 楼

我用priority queue，他不让。他说我的目的就是要让你实现heap

【在 w*******s 的大作中提到】

: 这个是amortized O(n)的算法，所以不需要用heap，不过老印不让用STL也挺奇怪的
: 解答leetcode上有：http://leetcode.com/2011/01/sliding-window-maximum.html
:
: leftmost

w*s2013-12-12 08:12

9 楼

汗，那只能现写了，不过写完了他也会说做法不够好

【在 p*u 的大作中提到】

: 我用priority queue，他不让。他说我的目的就是要让你实现heap