Leetcode 第155题 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。 pop() —— 删除栈顶的元素。 top() —— 获取栈顶元素。 getMin() —— 检索栈中的最小元素。

示例:

输入： ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]

输出： [null,null,null,null,-3,null,0,-2]

解释： MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.

提示：

• pop、top 和 getMin 操作总是在 非空栈 上调用

解题思路

这道题目主要考察数据结构,实现起来也很简单 我们定义一个额外的栈 存放最小值,比较下 比辅助栈内元素小的话 就入栈。

入栈 3 | | | | | | | | |3| |3| stack minStack

入栈 5 ， 5 大于 minStack 栈顶，不处理 | | | | | 5 | | | |3| |3| stack minStack

入栈 2 ，此时右边的 minStack 栈顶就保存了当前最小值 2 | 2 | | | | 5 | | 2 | |3| |3| stack minStack

出栈 2，此时右边的 minStack 栈顶就保存了当前最小值 3 | | | | | 5 | | | |3| |3| stack minStack

出栈 5，右边 minStack 不处理 | | | | | | | | |3| |3| stack minStack

出栈 3 | | | | | | | | |_ | | _| stack minStack

这道题可以帮助我们 熟悉如何用 Rust 栈 数据结构我们用Vec 数组来存储栈元素。

struct MinStack {
    stack:Vec<i32>,
    minstack:Vec<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![],
            minstack: vec![],
        }
    }

    fn push(&mut self, x: i32) {
        self.stack.push(x);
        if self.minstack.len() == 0 ||
            x <= self.get_min(){  self.minstack.push(x)
        }

    }

    fn pop(&mut self) {
        if self.stack[self.stack.len()-1] == self.minstack[self.minstack.len()-1] {
            self.minstack.remove(self.minstack.len()-1);

        }
        self.stack.remove(self.stack.len()-1);

    }

    fn top(&self) -> i32 {

        self.stack[self.stack.len()-1]
    }

    fn get_min(&self) -> i32 {
        if self.minstack.len() ==0 {  return 0;}
        self.minstack[self.minstack.len()-1]
    }
}