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
andgetMin
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.