How would you design a stack which, in addition to push and pop, also has a function min which return minimum element? Push, pop and min should all operate in O(1) time.
How to Solve
By keeping a minimum value at each state, we can know the minimum value easily. So, we define a additional stack which keeps minimum value at each state as a member in Stack Class like this.
And when we push or pop, we have to operate the following processing.
- In push case: if inputting value is a minimum value at current state, we push it into minStack
- In pop case: if outputting value is a minimum value at current state, we pop it from minStack
From the above, we can get a minimum value in O(1) time.