⚡Flashcard Drill➔
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

  1. A plain list supports push, pop and top in O(1), and peekMax in O(n).
  2. popMax needs to remove the topmost occurrence of the maximum, which is the last occurrence in list order.
  3. Finding that index is len(st) - 1 - st[::-1].index(m).
  4. 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 peekMax must 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.
🎯 Drill This Card Now➔

🧩 Related Stack Problems