Earlier quoted context omitted.
> With O(1) time, the easiest solution is just to store the minimum-to-date next to the value in the stack. Consulting the minimum is then just looking at the top value's minimum entry. That won’t work. The all-time minimum may have been popped when the call to retrieve the lowest value currently on the stack is made. As a first go, I would use a min-heap ( https://en.wikipedia.org/wiki/Heap_(data_structure) ) and a…
The original post may have some ambiguity in the term "minimum" but I read it as the minimum of the current contents of the stack, based on where the link the OP provided went to. When I said "minimum to date", I meant relative to the current contents of the stack in order. That is, if you push a value larger than the minimum on the top of the stack, you copy the minimum, if it's smaller, the pushed entry on the stac…
Re: How do you guys come up with such an algorithm
#21Sorry, misinterpreted ”store the minimum-to-date next to the value in the stack”, reading it as if you had the stack and, next to it, a single “minimum to date” value.