Design a MinStack class that supports push(val), pop(), top() and getMin(), where getMin() returns the smallest element currently in the stack. Every operation must run in O(1) time. pop, top and getMin are only called on a non-empty stack.
- -2^31 <= val <= 2^31 - 1
- At most 3 * 10^4 calls in total
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force scans the whole stack inside getMin, which is O(n). A single running minimum is not enough because popping the smallest element would force a rescan. The fix is to remember history: each stack entry stores its value together with the minimum of everything at or below it. Since a stack only changes at the top, that saved minimum stays correct, and getMin simply reads it from the top entry.
Algorithm
- Keep a stack of pairs
(value, minSoFar). push(val): the new minimum isvalif the stack is empty, otherwisemin(val, top.minSoFar); push the pair.pop(): remove the top pair.top(): return the value of the top pair;getMin(): return itsminSoFar.
O(1) per operationSpace: O(n)val - min in a long and update min when the difference is negative. Mention that it needs 64-bit values to avoid overflow with -2^31.class MinStack: def __init__(self): # Each entry is (value, minimum of the stack up to and including this entry). self.stack = [] def push(self, val: int) -> None: cur_min = val if not self.stack else min(val, self.stack[-1][1]) self.stack.append((val, cur_min)) def pop(self) -> None: self.stack.pop() def top(self) -> int: return self.stack[-1][0] def getMin(self) -> int: return self.stack[-1][1]