CareerCup question - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

CareerCup question

CareerCup question# JobHunting - 待字闺中

c*e2012-01-10 08:01

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*w2012-01-10 08:01

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*c2012-01-10 08:01

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*e2012-01-10 08:01

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*c2012-01-10 08:01

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.