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:
|
