Use two stacks and keep track of the min so far in it at each level. Make sure the push and pop syncs the min stack and make it same length.

the min object can be anywhere inside it, you have to go through all of the stack and search for it (doesn't matter which way you go through it...) which means O(n), or am I missing something?