a*****g 发帖数: 22 | 1 An interview question. I proposed using two stacks, whenever changing action
(pop->push or push->pop), put all data from one stack to the other. I was
told it was too slow.
Any idea? thanks | t****t 发帖数: 6806 | 2 一个明显的改进是这样, 每次朝stack A里push (push stack).
pop时,从stack B (pop stack) pop. 如果pop时遇到B为空,则把A搬到B.
这样平均复杂度还是O(1). 不过不能保证每个操作都是O(1).
action
【在 a*****g 的大作中提到】 : An interview question. I proposed using two stacks, whenever changing action : (pop->push or push->pop), put all data from one stack to the other. I was : told it was too slow. : Any idea? thanks
|
|