| 73 | |
| 74 | impl MaxNumber { |
| 75 | pub fn new(mut stack: Vec<i32>) -> MaxNumber { |
| 76 | let mut tmp = MaxNumber { max_vec: Vec::with_capacity(stack.len() + 1) }; |
| 77 | // Question: is push_front of VecDeque a O(1) operation ? |
| 78 | let mut i = 0; |
| 79 | tmp.max_vec.push(Some(stack.clone())); |
| 80 | for _ in 1..stack.len() { |
| 81 | while i + 1 < stack.len() && stack[i + 1] <= stack[i] { |
| 82 | i += 1 |
| 83 | } |
| 84 | if i >= stack.len() { stack.pop(); tmp.max_vec.insert(0, Some(stack.clone())) } |
| 85 | else { stack.remove(i); tmp.max_vec.insert(0, Some(stack.clone())) } |
| 86 | if i > 0 { i -= 1 } |
| 87 | } |
| 88 | tmp.max_vec.insert(0, None); |
| 89 | tmp |
| 90 | } |
| 91 | |
| 92 | pub fn get(&self, i: usize) -> Option<Vec<i32>> { |
| 93 | self.max_vec[i].clone() |