1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92
//! Min Stack [leetcode: min_stack](https://leetcode.com/problems/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. //! //! ***Example1:*** //! //! ``` //! MinStack minStack = new MinStack(); //! minStack.push(-2); //! minStack.push(0); //! minStack.push(-3); //! minStack.getMin(); --> Returns -3. //! minStack.pop(); //! minStack.top(); --> Returns 0. //! minStack.getMin(); --> Returns -2. //! //! ``` /// # Solutions /// /// # Approach 1: /// /// * Time complexity: O(1) /// /// * Space complexity: O(n) /// /// * Runtime: 0 ms /// * Memory: 5.2 MB /// /// ```rust /// struct MinStack { /// stack: Vec<i32>, /// min: i32, /// } /// /// /** /// * `&self` means the method takes an immutable reference. /// * If you need a mutable reference, change it to `&mut self` instead. /// */ /// impl MinStack { /// /// /** initialize your data structure here. */ /// fn new() -> Self { /// MinStack { /// stack: vec![], /// min: i32::max_value(), /// } /// } /// /// fn push(&mut self, x: i32) { /// if self.min >= x { /// self.stack.push(self.min); /// self.min = x; /// } /// self.stack.push(x); /// } /// /// fn pop(&mut self) { /// if let Some(i) = self.stack.pop() { /// if i == self.min { self.min = self.stack.pop().unwrap(); } /// } /// } /// /// fn top(&self) -> i32 { /// *self.stack.last().unwrap() /// } /// /// fn get_min(&self) -> i32 { /// self.min /// } /// } /// /// /** /// * Your MinStack object will be instantiated and called as such: /// * let obj = MinStack::new(); /// * obj.push(x); /// * obj.pop(); /// * let ret_3: i32 = obj.top(); /// * let ret_4: i32 = obj.get_min(); /// */ /// ``` /// #[allow(dead_code)] pub struct MinStack { stack: Vec<i32>, min: i32, }