155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

  • push(x) -- Push element x onto stack.
  • pop() -- Removes the element on top of the stack.
  • top() -- Get the top element.
  • getMin() -- Retrieve the minimum element in the stack.

 

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

 

Constraints:

  • Methods pop, top and getMin operations will always be called on non-empty stacks.

Rust Solution

#[derive(Default)]
struct MinStack {
    nums: Vec<i32>,
    mins: Vec<i32>,
    top: i32,
    min: i32,
}

impl MinStack {
    fn new() -> Self {
        MinStack {
            nums: vec![],
            mins: vec![],
            top: 0,
            min: 0,
        }
    }

    fn push(&mut self, x: i32) {
        self.nums.push(x);
        if let Some(&min) = self.mins.last() {
            self.mins.push(i32::min(x, min));
        } else {
            self.mins.push(x);
        }
        self.set_min();
        self.set_top();
    }

    fn pop(&mut self) {
        self.nums.pop();
        self.mins.pop();
        self.set_min();
        self.set_top();
    }

    fn set_top(&mut self) {
        self.top = if let Some(&last) = self.nums.last() {
            last
        } else {
            0
        }
    }

    fn set_min(&mut self) {
        self.min = if let Some(&last) = self.mins.last() {
            last
        } else {
            0
        }
    }

    fn top(&self) -> i32 {
        self.top
    }

    fn get_min(&self) -> i32 {
        self.min
    }
}

#[test]
fn test() {
    let mut min_stack = MinStack::new();
    min_stack.push(-2);
    min_stack.push(0);
    min_stack.push(-3);
    assert_eq!(min_stack.get_min(), -3);
    min_stack.pop();
    assert_eq!(min_stack.top(), 0);
    assert_eq!(min_stack.get_min(), -2);
}

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