Max stack

Linked List Stack Design Doubly-Linked List Ordered Set

45.9% acceptance

Mar 31, 2026

2015

513

Design a max stack data structure that supports the stack operations and supports finding the stack's maximum element. Implement the MaxStack class: MaxStack() Initializes the stack object. void push(int x) Pushes element x onto the stack. int pop() Removes the element on top of the stack and returns it. int top() Gets the element on the top of the stack without removing it. int peekMax() Retrieves the maximum element in the stack without removing it. int popMax() Retrieves the maximum element in the stack and removes it. If there is more than one maximum element, only remove the top-most one. You must come up with a solution that supports O(1) for each top call and O(logn) for each other call.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::collections::BTreeMap;

struct MaxStack {
  // stack: list of (value, id), sorted by insertion order
  // We use a BTreeMap<i32, Vec<u64>> for value -> ids (for popMax)
  // and a BTreeMap<u64, i32> for id -> value (for stack order)
  id_to_val: BTreeMap<u64, i32>,
  val_to_ids: BTreeMap<i32, Vec<u64>>,
  counter: u64,
}

impl MaxStack {
  fn new() -> Self {
    MaxStack {
      id_to_val: BTreeMap::new(),
      val_to_ids: BTreeMap::new(),
      counter: 0,
    }
  }
  
  fn push(&mut self, x: i32) {
    let id = self.counter;
    self.counter += 1;
    self.id_to_val.insert(id, x);
    self.val_to_ids.entry(x).or_insert_with(Vec::new).push(id);
  }
  
  fn pop(&mut self) -> i32 {
    let (&id, &val) = self.id_to_val.iter().next_back().unwrap();
    self.id_to_val.remove(&id);
    let ids = self.val_to_ids.get_mut(&val).unwrap();
    ids.retain(|&i| i != id);
    if ids.is_empty() {
      self.val_to_ids.remove(&val);
    }
    val
  }
  
  fn top(&self) -> i32 {
    let (_, &val) = self.id_to_val.iter().next_back().unwrap();
    val
  }
  
  fn peek_max(&self) -> i32 {
    let (&val, _) = self.val_to_ids.iter().next_back().unwrap();
    val
  }
  
  fn pop_max(&mut self) -> i32 {
    let (&val, ids) = self.val_to_ids.iter_mut().next_back().unwrap();
    let id = ids.pop().unwrap();
    if ids.is_empty() {
      self.val_to_ids.remove(&val);
    }
    self.id_to_val.remove(&id);
    val
  }
}