マツシタのお勉強

Implement function min which returns minimum element in stack

Problem

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.

Source Code