Design a stack which satisfies the push, pop, min with O(1)

Problem Description

Design a stack which satisfies the push, pop, min with O(1).

Analysis

Regular stack can easily fulfill the operation of push or pop with O(1).

However, an usual stack could not satisfy min with O(1).

If we use a single variable to storage the min value in the stack, it will cost O(n) to maintain the variable stores the min value when we push or pop value. (Need to scan the whole stack to find another min value.)

Thus, we use another stack to fulfill the min operation with O(1).

(The second stack stores the min value corresponds to the new push number.)

My Solution:

Push:

1. Push the number into the data stack as usual.

2. Compare the new push number with the top number in the min value stack.

(1)  If the min value stack is empty, just put the new push number into the min value stack.

(2) If the top number in the min value stack is smaller than the new push number, push the new push number into the min value stack.

(3) If the top number in the min value stack is larger than the new push number, copy the top number of the min value stack and push it into the min value stack.

 

For example,

If we push 2,6,4,1,5, the two stack (an usual stack and a stack store the min numbers) will be :

Stack A       Stack B（min value stack）

5                    1

1                    1

4                    2

6                    2

2                    2

 

Pop:

1. Pop the number into the data stack as usual.

2. Pop the top number in the min value stack.

 

Min:

Get the top number of the min value stack.