155. Min Stack Medium

1/**
2 * [155] Min Stack
3 *
4 * Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
5 * Implement the MinStack class:
6 * 
7 * MinStack() initializes the stack object.
8 * void push(int val) pushes the element val onto the stack.
9 * void pop() removes the element on the top of the stack.
10 * int top() gets the top element of the stack.
11 * int getMin() retrieves the minimum element in the stack.
12 * 
13 *  
14 * Example 1:
15 * 
16 * Input
17 * ["MinStack","push","push","push","getMin","pop","top","getMin"]
18 * [[],[-2],[0],[-3],[],[],[],[]]
19 * Output
20 * [null,null,null,null,-3,null,0,-2]
21 * Explanation
22 * MinStack minStack = new MinStack();
23 * minStack.push(-2);
24 * minStack.push(0);
25 * minStack.push(-3);
26 * minStack.getMin(); // return -3
27 * minStack.pop();
28 * minStack.top();    // return 0
29 * minStack.getMin(); // return -2
30 * 
31 *  
32 * Constraints:
33 * 
34 * -2^31 <= val <= 2^31 - 1
35 * Methods pop, top and getMin operations will always be called on non-empty stacks.
36 * At most 3 * 10^4 calls will be made to push, pop, top, and getMin.
37 * 
38 */
39pub struct Solution {}
40
41// problem: https://leetcode.com/problems/min-stack/
42// discuss: https://leetcode.com/problems/min-stack/discuss/?currentPage=1&orderBy=most_votes&query=
43
44// submission codes start here
45
46struct MinStack {
47    data: Vec<i32>,
48    min: Vec<i32>
49}
50
51
52/** 
53 * `&self` means the method takes an immutable reference.
54 * If you need a mutable reference, change it to `&mut self` instead.
55 */
56use std::cmp;
57impl MinStack {
58    fn new() -> Self {
59        MinStack { data: Vec::new(), min: Vec::new() }
60    }
61    
62    fn push(&mut self, val: i32) {
63        self.data.push(val);
64        
65        match self.min.last() {
66            None => {
67                self.min.push(val);
68            },
69            Some(l) => {
70                // #[warn(mutable_borrow_reservation_conflict)]
71                let x = *l;
72                self.min.push(cmp::min(x, val));
73            }
74        }
75    }
76    
77    fn pop(&mut self) {
78        self.data.pop();
79        self.min.pop();
80    }
81    
82    fn top(&self) -> i32 {
83        match self.data.last() {
84            Some(l) => *l,
85            None => -1
86        }
87    }
88    
89    fn get_min(&self) -> i32 {
90        match self.min.last() {
91            Some(l) => *l,
92            None => i32::MAX
93        }
94    }
95}
96
97/**
98 * Your MinStack object will be instantiated and called as such:
99 * let obj = MinStack::new();
100 * obj.push(val);
101 * obj.pop();
102 * let ret_3: i32 = obj.top();
103 * let ret_4: i32 = obj.get_min();
104 */
105
106// submission codes end
107
108#[cfg(test)]
109mod tests {
110    use super::*;
111
112    #[test]
113    fn test_155() {
114        let mut obj = MinStack::new();
115        obj.push(1);
116        obj.push(4);
117        obj.push(2);
118        obj.push(8);
119        obj.pop();
120        obj.push(5);
121        assert_eq!(obj.top(), 5);
122        assert_eq!(obj.get_min(), 1);
123    }
124}
125