Why it works
- The entries under an entry never change while it is on the stack: they can only change after it is popped. So the low written when it was pushed stays right for as long as it stays.
- The low of a new entry is the smaller of its value and the low just below it, so getMin is the top's low: one lookup.
- A pop takes its low away with it, and the entry below already holds the minimum without it. That is why one minimum variable is not enough and a repeated minimum needs no counting.
Complexity
Time O(1) for every call: each one reads or changes only the top. Memory O(n) for n entries, two numbers each.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗