716. Max Stack

Design a max stack data structure that supports the stack operations and supports finding the stack's maximum element.

Implement the `MaxStack` class:

• `MaxStack()` Initializes the stack object.
• `void push(int x)` Pushes element `x` onto the stack.
• `int pop()` Removes the element on top of the stack and returns it.
• `int top()` Gets the element on the top of the stack without removing it.
• `int peekMax()` Retrieves the maximum element in the stack without removing it.
• `int popMax()` Retrieves the maximum element in the stack and removes it. If there is more than one maximum element, only remove the top-most one.

Example 1:

```Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]

Explanation
MaxStack stk = new MaxStack();
stk.push(5);   // [5] the top of the stack and the maximum number is 5.
stk.push(1);   // [5, 1] the top of the stack is 1, but the maximum is 5.
stk.push(5);   // [5, 1, 5] the top of the stack is 5, which is also the maximum, because it is the top most one.
stk.top();     // return 5, [5, 1, 5] the stack did not change.
stk.popMax();  // return 5, [5, 1] the stack is changed now, and the top is different from the max.
stk.top();     // return 1, [5, 1] the stack did not change.
stk.peekMax(); // return 5, [5, 1] the stack did not change.
stk.pop();     // return 1, [5] the top of the stack and the max element is now 5.
stk.top();     // return 5, [5] the stack did not change.
```

Constraints:

• `-107 <= x <= 107`
• At most `104` calls will be made to `push`, `pop`, `top`, `peekMax`, and `popMax`.
• There will be at least one element in the stack when `pop`, `top`, `peekMax`, or `popMax` is called.

Follow up: Could you come up with a solution that supports `O(1)` for each `top` call and `O(logn)` for each other call?

716. Max Stack
``````use std::i32;

#[derive(Default)]
struct MaxStack {
vec: Vec<i32>,
}

impl MaxStack {
fn new() -> Self {
MaxStack { vec: vec![] }
}

fn push(&mut self, x: i32) {
self.vec.push(x);
}

fn pop(&mut self) -> i32 {
self.vec.pop().unwrap()
}

fn top(&self) -> i32 {
*self.vec.last().unwrap()
}

fn peek_max(&self) -> i32 {
let mut max = self.top();
for &x in &self.vec {
max = i32::max(max, x);
}
max
}

fn pop_max(&mut self) -> i32 {
let mut index = self.vec.len() - 1;
let mut max = self.top();
let n = self.vec.len();
for i in 0..n {
let j = n - 1 - i;
let x = self.vec[j];
if x > max {
max = x;
index = j;
}
}
self.vec.remove(index);
max
}
}

#[test]
fn test() {
let mut stack = MaxStack::new();
stack.push(5);
stack.push(1);
stack.push(5);
assert_eq!(stack.top(), 5);
assert_eq!(stack.pop_max(), 5);
assert_eq!(stack.top(), 1);
assert_eq!(stack.peek_max(), 5);
assert_eq!(stack.pop(), 1);
assert_eq!(stack.top(), 5);
}
``````