Alongside the values, keep a parallel stack whose top is always the minimum so far. Because they push and pop together, the current minimum is one lookup away.