Sorry for being picky. But I think it seems impossible to retain the trace of getMin() after several pop() in time of O(1).
Please enlighten me if you get any idea
Initial: s = [3, 2, 1, -1] getMin() // -1 pop() // s = [3, 2, 1] getMin() // should be 1 at index 2
But how can we find this index in linear time?
We can introduce another pointer preMin, but what if there is another pop()?
Continue: pop() // s = [3, 2] getMin() // should be 2 at index 1
if seems to get chained up by the number of calling of pop()
We might have another sorted list/array/vector to keep track of the elements have been pushed into MinStack. But I believe it would introduce extra cost to push() method and boost the time complexity to O(lg(n))(e,g, binary search).
Maintaining an extra list to obtain Min from the stack will cost you, but not as much as calling the min function on the whole stack. Here's my code, check it out. stack_min will always have min element at the end, at any given point of time. Complexity is O(1) here.
class MinStack(object): def __init__(self): self.stack= self.stack_min=[float('Inf')] def push(self, x): self.stack.append(x) self.stack_min.append(min(self.stack_min[-1],x)) def pop(self): if self.stack: self.stack.pop() self.stack_min.pop() def top(self): return self.stack[-1] def getMin(self): return self.stack_min[-1]