L*******e 发帖数: 114 | 1 Implement a queue in which push_rear(), pop_front() and get_min() are all
constant time operations。
Copied from careercup. seemed no good solution discussed over there. 高手
share一下?thanks. |
g*********s 发帖数: 1782 | 2 no, the commonly asked one is the stack, not the queue.
the hardness of queue is due to the fact the queue has 2 ends to take care
while the stack only have one.
it's an interesting variant of the classical one. but i don't feel there's
any good algo.
all
【在 L*******e 的大作中提到】 : Implement a queue in which push_rear(), pop_front() and get_min() are all : constant time operations。 : Copied from careercup. seemed no good solution discussed over there. 高手 : share一下?thanks.
|
L*******e 发帖数: 114 | 3 Thanks. Then what is the solution for stack? using a priority_queue? |
f*******4 发帖数: 1401 | 4 Use an extra stack to maintain the minimums.
To retrieve the current minimum, just return the top element from minimum
stack.
Each time you perform a push operation, check if the pushed element is a new
minimum. If it is, push it to the minimum stack too.
When you perform a pop operation, check if the popped element is the same as
the current minimum. If it is, pop it off the minimum stack too. |
D*********y 发帖数: 876 | 5 对
这是career cup 150题里面的一个例题
我记得programming interview那本书里也讲到了这道题
new
as
【在 f*******4 的大作中提到】 : Use an extra stack to maintain the minimums. : To retrieve the current minimum, just return the top element from minimum : stack. : Each time you perform a push operation, check if the pushed element is a new : minimum. If it is, push it to the minimum stack too. : When you perform a pop operation, check if the popped element is the same as : the current minimum. If it is, pop it off the minimum stack too.
|
i**********e 发帖数: 1145 | 6 这题用两个 queue 就行了。
一个 queue 来 maintain minimums,另一个 queue 来 push_rear 和 pop_front.
每次 push 一个新元素的时候,检查 min queue 的后面的值是否大于新值。如果是的
话,就一直 pop,直到后边值小于或者等于新值(或者 min queue 为空)。
每次 pop_front 的时候,就检查现在 pop 的元素是否与 current min 相等。如果是
的话,就从 queue 和 min queue 同时 pop.
其实这是 google 经典题 finding sliding window minimum/maximum 的变种。
因为同样一个 data structure 就直接能应用于 finding sliding window minimum,
并且得到 O(N) 的复杂度。
Reference:
http://www.ihas1337code.com/2010/11/stack-that-supports-push-po
http://www.ihas1337code.com/2011/01/sliding-window-maximum.html
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
c********t 发帖数: 5706 | 7 好像不太对啊。比如 1,3,2 按描述
每次 push 一个新元素的时候,检查 min queue 的后面的值是否大于新值。如果是的
话,就一直 pop,直到后边值小于或者等于新值(或者 min queue 为空)。
那么 到2入queue的时候,min queue里面是(1,3),2>1,所以2就直接入min queue
,变为(1,3,2),就不对了。
sliding window我没见过,就去搜了一下,好像用的是vector, 要去掉vector中所有比
新值大的的元素,而不是只比较最后的元素吧?
【在 i**********e 的大作中提到】 : 这题用两个 queue 就行了。 : 一个 queue 来 maintain minimums,另一个 queue 来 push_rear 和 pop_front. : 每次 push 一个新元素的时候,检查 min queue 的后面的值是否大于新值。如果是的 : 话,就一直 pop,直到后边值小于或者等于新值(或者 min queue 为空)。 : 每次 pop_front 的时候,就检查现在 pop 的元素是否与 current min 相等。如果是 : 的话,就从 queue 和 min queue 同时 pop. : 其实这是 google 经典题 finding sliding window minimum/maximum 的变种。 : 因为同样一个 data structure 就直接能应用于 finding sliding window minimum, : 并且得到 O(N) 的复杂度。 : Reference:
|
i**********e 发帖数: 1145 | 8 是检查minqueue 的后面,不时前面。
minqueue = [1, 3], push 2 的时候,因为 3 > 2,pop 3 from back,然后再比较 1
和 2. 因为 1 <= 2,那就把 2 push 进 minqueue。这时候 minqueue = [1, 2].
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
queue
【在 c********t 的大作中提到】 : 好像不太对啊。比如 1,3,2 按描述 : 每次 push 一个新元素的时候,检查 min queue 的后面的值是否大于新值。如果是的 : 话,就一直 pop,直到后边值小于或者等于新值(或者 min queue 为空)。 : 那么 到2入queue的时候,min queue里面是(1,3),2>1,所以2就直接入min queue : ,变为(1,3,2),就不对了。 : sliding window我没见过,就去搜了一下,好像用的是vector, 要去掉vector中所有比 : 新值大的的元素,而不是只比较最后的元素吧?
|
g*********s 发帖数: 1782 | 9 in this case how u ensure O(1)?
1
【在 i**********e 的大作中提到】 : 是检查minqueue 的后面,不时前面。 : minqueue = [1, 3], push 2 的时候,因为 3 > 2,pop 3 from back,然后再比较 1 : 和 2. 因为 1 <= 2,那就把 2 push 进 minqueue。这时候 minqueue = [1, 2]. : 一些常见面试题的答案与总结 - : http://www.ihas1337code.com : : queue
|
m****i 发帖数: 650 | 10
minimum
new
same as
这个解对所有数字unique有效,如果可以duplication.那要小改一下
【在 f*******4 的大作中提到】 : Use an extra stack to maintain the minimums. : To retrieve the current minimum, just return the top element from minimum : stack. : Each time you perform a push operation, check if the pushed element is a new : minimum. If it is, push it to the minimum stack too. : When you perform a pop operation, check if the popped element is the same as : the current minimum. If it is, pop it off the minimum stack too.
|
|
|
c********t 发帖数: 5706 | 11 赞!明白了!
不过push rear 的操作不能保证是O(1)吧。极端的情况可能是O(n), 比如 2,3,4,5
,1. push 1的时候,要在min queue比较删除前4个
1
【在 i**********e 的大作中提到】 : 是检查minqueue 的后面,不时前面。 : minqueue = [1, 3], push 2 的时候,因为 3 > 2,pop 3 from back,然后再比较 1 : 和 2. 因为 1 <= 2,那就把 2 push 进 minqueue。这时候 minqueue = [1, 2]. : 一些常见面试题的答案与总结 - : http://www.ihas1337code.com : : queue
|
c********t 发帖数: 5706 | 12 只要小于等于minimum top的都push into stack就好了
【在 m****i 的大作中提到】 : : minimum : new : same as : 这个解对所有数字unique有效,如果可以duplication.那要小改一下
|
i**********e 发帖数: 1145 | 13 你说的没错,依你这种最坏情况在 push 1 的时候是 O(N),但是其余的 operations
都是 O(1)的。而这最坏的情况是出现于在 push 了 N 个元素之后,在 push 一个最
小值,使得这个 operation 为 O(N).根据 amortized analysis,这平均复杂度为 O(N
)/N = O(1).当 push 了这个最小值之后,又不可能立刻出现 O(N) 的状况了。
请参考:
http://en.wikipedia.org/wiki/Amortized_analysis
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
,5
【在 c********t 的大作中提到】 : 赞!明白了! : 不过push rear 的操作不能保证是O(1)吧。极端的情况可能是O(n), 比如 2,3,4,5 : ,1. push 1的时候,要在min queue比较删除前4个 : : 1
|
c********t 发帖数: 5706 | 14 多谢,多谢!
(N
【在 i**********e 的大作中提到】 : 你说的没错,依你这种最坏情况在 push 1 的时候是 O(N),但是其余的 operations : 都是 O(1)的。而这最坏的情况是出现于在 push 了 N 个元素之后,在 push 一个最 : 小值,使得这个 operation 为 O(N).根据 amortized analysis,这平均复杂度为 O(N : )/N = O(1).当 push 了这个最小值之后,又不可能立刻出现 O(N) 的状况了。 : 请参考: : http://en.wikipedia.org/wiki/Amortized_analysis : 一些常见面试题的答案与总结 - : http://www.ihas1337code.com : : ,5
|
e******a 发帖数: 176 | 15 ihasleetcode, 我怎么觉得第二个用来存minimums的queue, 跟任何时候只保持当前
minimum相比,没有什么优势呢?原因是这样的:
如果旧的minimum被pop了,要找新的minimum, 如果新的min离对头很近,也不用O(n),
如果离得很远,是要O(n), 但是这种情况下,你的push_rear()操作也要O(n),因为你从
min queue里pop走了很多比新的min大的元素。
所以说,只keep record of current min有类似O(1)的复杂度.请问是这样么?谢谢 |
e******a 发帖数: 176 | 16 对 1,2,3,4,5,6 输入序列,ihasleetcode 你的复杂度是 O(1)的,我的是O(n)的
。 |
h**k 发帖数: 3368 | 17 这里用来保存minimums的不能是queue,因为queue严格讲只提供了两个操作,从前面
pop()和从后面push()。你不能从一
个queue的后面pop。这里可以用doubly linked list来做这个。
【在 i**********e 的大作中提到】 : 这题用两个 queue 就行了。 : 一个 queue 来 maintain minimums,另一个 queue 来 push_rear 和 pop_front. : 每次 push 一个新元素的时候,检查 min queue 的后面的值是否大于新值。如果是的 : 话,就一直 pop,直到后边值小于或者等于新值(或者 min queue 为空)。 : 每次 pop_front 的时候,就检查现在 pop 的元素是否与 current min 相等。如果是 : 的话,就从 queue 和 min queue 同时 pop. : 其实这是 google 经典题 finding sliding window minimum/maximum 的变种。 : 因为同样一个 data structure 就直接能应用于 finding sliding window minimum, : 并且得到 O(N) 的复杂度。 : Reference:
|
i**********e 发帖数: 1145 | 18 恩,对。
如果 double ended queue 应该可以吧。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 h**k 的大作中提到】 : 这里用来保存minimums的不能是queue,因为queue严格讲只提供了两个操作,从前面 : pop()和从后面push()。你不能从一 : 个queue的后面pop。这里可以用doubly linked list来做这个。
|
s**********v 发帖数: 1379 | 19 en, 和那个stack的题目思路类似..
【在 i**********e 的大作中提到】 : 这题用两个 queue 就行了。 : 一个 queue 来 maintain minimums,另一个 queue 来 push_rear 和 pop_front. : 每次 push 一个新元素的时候,检查 min queue 的后面的值是否大于新值。如果是的 : 话,就一直 pop,直到后边值小于或者等于新值(或者 min queue 为空)。 : 每次 pop_front 的时候,就检查现在 pop 的元素是否与 current min 相等。如果是 : 的话,就从 queue 和 min queue 同时 pop. : 其实这是 google 经典题 finding sliding window minimum/maximum 的变种。 : 因为同样一个 data structure 就直接能应用于 finding sliding window minimum, : 并且得到 O(N) 的复杂度。 : Reference:
|