d*********g
发帖数: 59 | 1 一个stack, with push, pop, min()三个method，问如何设计min使效率最高
我说把push设计为每次输入都比较转换，2，3，5，6，10这样最上面都是最小的元素。
好像还不满意，不知道还有没有更好的设计方法？ | h**********d
发帖数: 4313 | | d*********g
发帖数: 59 | 3 用两个stack如何能够实现push,pop,min都是O（1）？如果min是O（1）那么push肯定要
至少Log(N)啊，输入是random的integer3,6,2,8, 5, 10这样 | w****m
发帖数: 146 | 4 another stack just keeps the current min information.
And it updates only when minimum element in the stack changes(a number
smaller than current minimum pushes in or current minimum pops out)
【在 d*********g 的大作中提到】
: 用两个stack如何能够实现push,pop,min都是O（1）？如果min是O（1）那么push肯定要
: 至少Log(N)啊，输入是random的integer3,6,2,8, 5, 10这样
| f****g
发帖数: 313 | | j*****u
发帖数: 1133 | 6
【在 d*********g 的大作中提到】
: 一个stack, with push, pop, min()三个method，问如何设计min使效率最高
: 我说把push设计为每次输入都比较转换，2，3，5，6，10这样最上面都是最小的元素。
: 好像还不满意，不知道还有没有更好的设计方法？
| j*****u
发帖数: 1133 | 7 two stacks, one to keep min and push/pop together
or one stack but every item has a local min, i.e.
class MinStack
{
Stack stack;
private class StackItem
{
public T Data { get; set;}
public T LocalMin { get; set;}
}
}
【在 d*********g 的大作中提到】
: 一个stack, with push, pop, min()三个method，问如何设计min使效率最高
: 我说把push设计为每次输入都比较转换，2，3，5，6，10这样最上面都是最小的元素。
: 好像还不满意，不知道还有没有更好的设计方法？
| d*********g
发帖数: 59 | | t****0
发帖数: 235 | 9 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.
seems not correct -
how about the popped up element is not current minimum but another element
in the minimum stack.
next time when a current minimum is popped out, an incorrect current
minimum might be used from the minimum stack.
【在 d*********g 的大作中提到】
: 好方法
| t****0
发帖数: 235 | 10 this is not possible. suppose there is such an element in the minimum stack
- then it must be pushed into minimum stack earlier then current minimum.
Therefore it is pushed into the regular stack earlier then current minimum...
this is correct.
【在 t****0 的大作中提到】
: 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.
: seems not correct -
: how about the popped up element is not current minimum but another element
: in the minimum stack.
: next time when a current minimum is popped out, an incorrect current
: minimum might be used from the minimum stack.
|
|
