716. Max Stack

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.

 

Example 1:

Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]

Explanation
MaxStack stk = new MaxStack();
stk.push(5);   // [5] the top of the stack and the maximum number is 5.
stk.push(1);   // [5, 1] the top of the stack is 1, but the maximum is 5.
stk.push(5);   // [5, 1, 5] the top of the stack is 5, which is also the maximum, because it is the top most one.
stk.top();     // return 5, [5, 1, 5] the stack did not change.
stk.popMax();  // return 5, [5, 1] the stack is changed now, and the top is different from the max.
stk.top();     // return 1, [5, 1] the stack did not change.
stk.peekMax(); // return 5, [5, 1] the stack did not change.
stk.pop();     // return 1, [5] the top of the stack and the max element is now 5.
stk.top();     // return 5, [5] the stack did not change.

 

Constraints:

  • -107 <= x <= 107
  • At most 104 calls will be made to push, pop, top, peekMax, and popMax.
  • There will be at least one element in the stack when pop, top, peekMax, or popMax is called.

 

Follow up: Could you come up with a solution that supports O(1) for each top call and O(logn) for each other call? 

Rust Solution

use std::i32;

#[derive(Default)]
struct MaxStack {
    vec: Vec<i32>,
}

impl MaxStack {
    fn new() -> Self {
        MaxStack { vec: vec![] }
    }

    fn push(&mut self, x: i32) {
        self.vec.push(x);
    }

    fn pop(&mut self) -> i32 {
        self.vec.pop().unwrap()
    }

    fn top(&self) -> i32 {
        *self.vec.last().unwrap()
    }

    fn peek_max(&self) -> i32 {
        let mut max = self.top();
        for &x in &self.vec {
            max = i32::max(max, x);
        }
        max
    }

    fn pop_max(&mut self) -> i32 {
        let mut index = self.vec.len() - 1;
        let mut max = self.top();
        let n = self.vec.len();
        for i in 0..n {
            let j = n - 1 - i;
            let x = self.vec[j];
            if x > max {
                max = x;
                index = j;
            }
        }
        self.vec.remove(index);
        max
    }
}

#[test]
fn test() {
    let mut stack = MaxStack::new();
    stack.push(5);
    stack.push(1);
    stack.push(5);
    assert_eq!(stack.top(), 5);
    assert_eq!(stack.pop_max(), 5);
    assert_eq!(stack.top(), 1);
    assert_eq!(stack.peek_max(), 5);
    assert_eq!(stack.pop(), 1);
    assert_eq!(stack.top(), 5);
}

Having problems with this solution? Click here to submit an issue on github.