I have a novel solution: use a delta ~~queue~~ stack! Instead of pushing straight numbers, push the delta of each new value against the next smaller value currently in the stack. Sadly I can't find a resource for this data structure. I learned about it in university when writing a sleep() function for an OS I was writing. On each tick, you simply decrement the first value (or pop it if it's 0).

[]

push(1) : [1]

push(2) : [1,1]

push(3) : [1,1,1]

push(3) : [1,1,1,0]

pop() : 3, [1,1,1]

pop() : 3, [1,1]

pop() : 2, [1]

pop() : 1 [0]

Have a few questions .. (1) doesn't it seem like this only works for elements that have an ordering as well a binary operation multiplication, subtraction and addition defined on them, making it too specific ? (I'm talking about the whole 2x - minelement) (2) If I have a variable hanging around a stack, is it still a stack? (3) When I pop out the min value in the stack, and want the next min Value, how do I get that,? seems like the previous min value still sticks around? (4) With comparisons and 1 value that hols state, do I really need to transform the values going into the stack?

Do you mean "design a stack where you can find the minimum value in O(1) both time and space complexity"? Because I don't see how you can do O(1) with an arbitrary stack.

What field of programming have you implemented that? I'm curios, is it in kernel development, some DB design. Not trolling, just curios where that usecase where this would come in handy and why ask it if it's not a direct relation to what you are doing.

Make another stack with the latest minimum, then when you pop that top value, you also pop it off the minimums stack. Then you have the last minimum before that one.

Is that it?