NeetCode #366LC-716HardStackNC Algo100
← Back to All Problems#366 · #716 · Max Stack(最大栈)
📌 Problem Statement & Constraints
Design a max stack supporting
push(x), pop(), top(), peekMax() and popMax(). popMax() removes and returns the maximum element; if there are several, remove the one closest to the top. Constraints: -10^7 <= x <= 10^7; at most 10^4 calls.💡 Core Algorithmic Approaches
- A plain list supports
push,popandtopin O(1), andpeekMaxin O(n). popMaxneeds to remove the topmost occurrence of the maximum, which is the last occurrence in list order.- Finding that index is
len(st) - 1 - st[::-1].index(m). - A fully optimal design uses a doubly linked list plus a sorted structure for O(log n) operations; the list version is far simpler and fast enough at these limits.
💻 Benchmark Python3 Implementation
class MaxStack:
def __init__(self):
self.st = []
def push(self, x: int) -> None:
self.st.append(x)
def pop(self) -> int:
return self.st.pop()
def top(self) -> int:
return self.st[-1]
def peekMax(self) -> int:
return max(self.st)
def popMax(self) -> int:
m = max(self.st)
# the topmost occurrence of the maximum is the LAST one in list order
i = len(self.st) - 1 - self.st[::-1].index(m)
return self.st.pop(i)
# Balanced-tree variant for O(log n) operations
class MaxStack2:
def __init__(self):
self.st = []
self.id = 0
self.heap = [] # (-value, -id) for max-first, top-first
self.removed = set()
def push(self, x: int) -> None:
import heapq
self.st.append((x, self.id))
heapq.heappush(self.heap, (-x, -self.id))
self.id += 1
def _clean(self) -> None:
import heapq
while self.heap and self.heap[0][1] in self.removed:
heapq.heappop(self.heap)
def pop(self) -> int:
v, i = self.st.pop()
self.removed.add(-i)
return v
def top(self) -> int:
return self.st[-1][0]
def peekMax(self) -> int:
self._clean()
return -self.heap[0][0]
def popMax(self) -> int:
self._clean()
negv, negi = self.heap[0]
i = -negi
self.removed.add(i)
# remove the specific entry from the stack
for k in range(len(self.st) - 1, -1, -1):
if self.st[k][1] == i:
self.st.pop(k)
break
return -negv⚡ Complexity Deep Dive
⏱️ Time Complexity
O(1) for push/pop/top and O(n) for peekMax/popMax in the list version. The heap variant achieves O(log n) amortised for all operations.
💾 Space Complexity
O(n).
⚠️ Interview Pitfalls & Follow-ups
- Removing the first occurrence of the maximum in
popMax: the requirement is the topmost one, i.e. the last occurrence in list order. - Using
st.index(m): that finds the first occurrence, which is the wrong one. - Assuming
peekMaxmust be O(1): the problem does not require it; only a full doubly-linked-list design would achieve that. - Forgetting the lazy-deletion set in the heap variant: stale heap entries would return removed values.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.