c**********e
发帖数: 2007 | 1 3.2 How would you design a stack which, in addition to push and pop, also
has a function min which returns the minimum element? Push, pop and min
should all operate in O(1) time.
I do not think it possible. The answer given seems wrong. Any comment?
Thanks. |
S*******w
发帖数: 24236 | 2 用数组做？
【在 c**********e 的大作中提到】
: 3.2 How would you design a stack which, in addition to push and pop, also
: has a function min which returns the minimum element? Push, pop and min
: should all operate in O(1) time.
: I do not think it possible. The answer given seems wrong. Any comment?
: Thanks.
|
q********c
发帖数: 1774 | 3 Use linked list for the stack. Push and pop would be O(1). Also update the
min value on every push then you can get MinVal in O(1). In the case that
you pop the min, scan the list to find the min and that would take O(n), but
it's not included in the MinVal operation so MinVal still takes O(1). |
c**********e
发帖数: 2007 | 4 Then pop() is not O(1). Did I miss anything?
but
【在 q********c 的大作中提到】
: Use linked list for the stack. Push and pop would be O(1). Also update the
: min value on every push then you can get MinVal in O(1). In the case that
: you pop the min, scan the list to find the min and that would take O(n), but
: it's not included in the MinVal operation so MinVal still takes O(1).
|
q********c
发帖数: 1774 | 5 Pop is still O(1) since you only get the head node from the list.Updating
min is not included in Pop. That's my understanding. |
k***t
发帖数: 276 | 6 Use two stacks internally.
【在 c**********e 的大作中提到】
: 3.2 How would you design a stack which, in addition to push and pop, also
: has a function min which returns the minimum element? Push, pop and min
: should all operate in O(1) time.
: I do not think it possible. The answer given seems wrong. Any comment?
: Thanks.
|
H***e
发帖数: 476 | 7 如果想好解释的话，就把stack中的数据增加一个field,用来存迄今为止最小的
这样每次pop也就可以看到了
【在 k***t 的大作中提到】
: Use two stacks internally.
|
r****t
发帖数: 10904 | 8 i think the answer is correct, it is not O(1) space, but it is O(1) time.
【在 c**********e 的大作中提到】
: 3.2 How would you design a stack which, in addition to push and pop, also
: has a function min which returns the minimum element? Push, pop and min
: should all operate in O(1) time.
: I do not think it possible. The answer given seems wrong. Any comment?
: Thanks.
|
x********3
发帖数: 160 | 9 Correct. Just find a way to store the min element corresponding to current
element.
【在 H***e 的大作中提到】
: 如果想好解释的话，就把stack中的数据增加一个field,用来存迄今为止最小的
: 这样每次pop也就可以看到了
|
c**********e
发帖数: 2007 | 10 Thank you guys. It is clear to me now. |
