NeetCode #350LC-155MediumStackNC 150NC 250
← Back to All Problems#350 · #155 · Min Stack(最小栈)
📌 Problem Statement & Constraints
Design a stack supporting
push, pop, top and getMin, all in O(1) time. Constraints: -2^31 <= val <= 2^31 - 1; at most 3 * 10^4 calls; pop, top and getMin are only called on a non-empty stack.💡 Core Algorithmic Approaches
- A single stack cannot answer
getMinin O(1) because popping the minimum would lose the next minimum. - Keep a parallel stack of running minima:
min_stack[i]is the minimum of the firsti + 1elements. - On
push, the new minimum ismin(val, current_min). Onpop, both stacks pop together. - An alternative encodes differences relative to the minimum to save space, but the parallel stack is far clearer.
💻 Benchmark Python3 Implementation
class MinStack:
def __init__(self):
self.st = []
self.mins = [] # running minimum at each depth
def push(self, val: int) -> None:
self.st.append(val)
self.mins.append(min(val, self.mins[-1] if self.mins else val))
def pop(self) -> None:
self.mins.pop() # keep the two stacks in sync
self.st.pop()
def top(self) -> int:
return self.st[-1]
def getMin(self) -> int:
return self.mins[-1]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(1) for every operation: one push or pop per stack.
💾 Space Complexity
O(n) for the two stacks.
⚠️ Interview Pitfalls & Follow-ups
- Recomputing
min(self.st)ingetMin: O(n) per call, defeating the purpose. - Storing only the current minimum: after popping it, the previous minimum is lost.
- Forgetting to keep the two stacks in sync:
popmust pop from both. - Initialising the minimum stack with a sentinel: using the conditional
if self.mins else valhandles the empty case without a magic value.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.