h****y
发帖数: 21 | 1 special stack, besides push/pop, can return the max number in the stack
the point is that all the performance of the three functions should be O(1)
Thank you for discussing |
c*****r
发帖数: 1491 | 2
use two stack
one for keeping the max
【在 h****y 的大作中提到】
: special stack, besides push/pop, can return the max number in the stack
: the point is that all the performance of the three functions should be O(1)
: Thank you for discussing
|
h****y
发帖数: 21 | 3 could you explaine the details?
notice that all the three function should be O(1)
【在 c*****r 的大作中提到】
:
: use two stack
: one for keeping the max
|
h****y
发帖数: 21 | 4 I've got it. Thank you:)
the second array is the sorted one to store pointers which can be pushed and
poped at the same time with the first stack, right?
【在 c*****r 的大作中提到】
:
: use two stack
: one for keeping the max
|
h****y
发帖数: 21 | 5 Also, the second array should be the double link list
and
【在 h****y 的大作中提到】
: I've got it. Thank you:)
: the second array is the sorted one to store pointers which can be pushed and
: poped at the same time with the first stack, right?
|
z****e
发帖数: 2024 | 6 two regular stack S1, S2.
for the special stack:
push(a){
S1.push(a);
max=S2.top();
S2.push(a>max?a:max);
}
pop(){
S1.pop();
S2.pop();
}
max(){
return S2.top();
}
top(){
return S1.top();
} |
g*******y
发帖数: 1930 | 7 for second stack, ith element record the max among 1st~ith element.
【在 h****y 的大作中提到】
: Also, the second array should be the double link list
:
: and
|
h****y
发帖数: 21 | 8 You are right , the sort algorithm can't be done in O(1)
we need another way.
one |
z****e
发帖数: 2024 | 9 anything wrong with my algorithm?
thank you in advance. |
h****y
发帖数: 21 | 10 this is the problem I got from this morning's amazon phone interview.
Do you think it's possible the interviewer ask an unsolvable question? |
|
|
z****e
发帖数: 2024 | 11 did you use the same method as mine?
【在 h****y 的大作中提到】
: this is the problem I got from this morning's amazon phone interview.
: Do you think it's possible the interviewer ask an unsolvable question?
|
z****e
发帖数: 2024 | 12 这个题目充分说明了，算法的面试，是没有办法准备的。
【在 h****y 的大作中提到】
: this is the problem I got from this morning's amazon phone interview.
: Do you think it's possible the interviewer ask an unsolvable question?
|
h****y
发帖数: 21 | 13 No, I think there is problem with your pop function
you need to keep the S1 and S2 pop the same element
My answer in the interview only can meet push O(1), pop O(n), max O(1)
by save and update the max element in the extra pointer
【在 z****e 的大作中提到】
: did you use the same method as mine?
|
h****y
发帖数: 21 | 14 that make sense. I've never think the interviewer's question can be
unsolvable before.
Next time, I will try to challenge them more:) |
h****y
发帖数: 21 | 15 it looks correct!
thank you so much:)
【在 z****e 的大作中提到】
: 这个题目充分说明了，算法的面试，是没有办法准备的。
|
z****e
发帖数: 2024 | 16 Actually, this reminds me that there is another problem saying:
use two stacks to maintain a queue, for Dequeue() and Enqueue(a) operation
with amortize O(1). |
p*********a
发帖数: 21 | 17 第二个stack用单调队列，只push和pop最大值， 空间上会更节省。 |
