p*u
发帖数: 136 | 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****m
发帖数: 179 | 2 sliding window哪到题需要用heap（不是deque）？能详细说一下吗？谢谢 | p*u
发帖数: 136 | 3 原帖已更新
【在 c****m 的大作中提到】
: sliding window哪到题需要用heap（不是deque）？能详细说一下吗？谢谢
| b*****c
发帖数: 1103 | 4 sliding max?
no heap, use deque | l******6
发帖数: 340 | 5 It would be better if you use two max stack to solve this problem | b*****c
发帖数: 1103 | | w*******s
发帖数: 138 | 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*u
发帖数: 136 | 8 我用priority queue，他不让。他说我的目的就是要让你实现heap
【在 w*******s 的大作中提到】
: 这个是amortized O(n)的算法，所以不需要用heap，不过老印不让用STL也挺奇怪的
: 解答leetcode上有：http://leetcode.com/2011/01/sliding-window-maximum.html
:
: leftmost
| w*******s
发帖数: 138 | 9 汗，那只能现写了，不过写完了他也会说做法不够好
【在 p*u 的大作中提到】
: 我用priority queue，他不让。他说我的目的就是要让你实现heap
| a*********0
发帖数: 2727 | 10 不就多考了怎么实现heap么。根本是基础知识呀
【在 p*u 的大作中提到】
: 我用priority queue，他不让。他说我的目的就是要让你实现heap
| b*****c
发帖数: 1103 | | J****3
发帖数: 427 | | t******g
发帖数: 1667 | 13 lz没搞清楚关键所在，还在纠结于技术层面。烙印根本没打算要你，就算你把问题解决
得再完美，他也可以找别的理由据你。move on | f*****d
发帖数: 209 | 14 这好好像是楼主自己做的不好吧，这个复杂度是O(n)
【在 t******g 的大作中提到】
: lz没搞清楚关键所在，还在纠结于技术层面。烙印根本没打算要你，就算你把问题解决
: 得再完美，他也可以找别的理由据你。move on
|
|
