0155. 最小栈 Min Stack

问题描述

这个问题可以有两种解法:

• 使用两个栈, 分别存放正常的数值, 和当前位置的最小值
• 使用一个栈, 但是栈中每个元素是一个元组, 分别存储 当前值和最小值

使用两个栈

Rust

#![allow(unused)]
fn main() {
// 用两个栈来实现
#[derive(Debug, Clone)]
pub struct MinStack {
    // 正常的栈, 按入栈顺序存储.
    stack: Vec<i32>,
    // 最小栈, 里面存储当前位置的最小元素, 最小元素可能是有重复的,
    // 其长度与 `stack` 相同.
    min_stack: Vec<i32>,
}

impl Default for MinStack {
    fn default() -> Self {
        Self::new()
    }
}

impl MinStack {
    #[must_use]
    #[inline]
    pub const fn new() -> Self {
        Self {
            stack: Vec::new(),

            min_stack: Vec::new(),
        }
    }

    pub fn push(&mut self, val: i32) {
        // 将元素入栈
        self.stack.push(val);
        if let Some(top) = self.min_stack.last() {
            // 保存当前位置最小的元素到 min_stack.
            self.min_stack.push(*top.min(&val));
        } else {
            self.min_stack.push(val);
        }
    }

    pub fn pop(&mut self) {
        let _ = self.stack.pop();
        let _ = self.min_stack.pop();
    }

    #[must_use]
    pub fn top(&self) -> i32 {
        self.stack.last().copied().unwrap_or_default()
    }

    #[must_use]
    pub fn get_min(&self) -> i32 {
        self.min_stack.last().copied().unwrap_or_default()
    }

    #[must_use]
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.stack.is_empty()
    }
}
}

C++

#include <cassert>

#include <stack>

class MinStack {
 public:
  MinStack() {}

  void push(int val) {
    this->stack_.push(val);
    if (this->min_stack_.empty()) {
      this->min_stack_.push(val);
    } else {
      const int current_min = this->min_stack_.top();
      const int new_min = std::min(current_min, val);
      this->min_stack_.push(new_min);
    }
  }

  void pop() {
    this->stack_.pop();
    this->min_stack_.pop();
  }

  int top() {
    return this->stack_.top();
  }

  int getMin() {
    return this->min_stack_.top();
  }

 private:
  std::stack<int> stack_;
  std::stack<int> min_stack_;
};

使用一个栈

Rust

#![allow(unused)]
fn main() {
// 用一个栈来实现
#[derive(Debug, Clone)]
pub struct MinStack {
    // 元组: (当前的元素, 当前最小的元素)
    stack: Vec<(i32, i32)>,
}

impl Default for MinStack {
    fn default() -> Self {
        Self::new()
    }
}

impl MinStack {
    #[must_use]
    #[inline]
    pub const fn new() -> Self {
        Self { stack: Vec::new() }
    }

    pub fn push(&mut self, val: i32) {
        if let Some(top) = self.stack.last() {
            let min = top.1.min(val);
            self.stack.push((val, min));
        } else {
            self.stack.push((val, val));
        }
    }

    pub fn pop(&mut self) {
        let _ = self.stack.pop().unwrap();
    }

    #[must_use]
    pub fn top(&self) -> i32 {
        self.stack.last().unwrap().0
    }

    #[must_use]
    pub fn get_min(&self) -> i32 {
        self.stack.last().unwrap().1
    }

    #[must_use]
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.stack.is_empty()
    }
}
}

C++

#include <cassert>

#include <stack>

class MinStack {
 public:
  MinStack() {}

  void push(int val) {
    if (this->stack_.empty()) {
      this->stack_.emplace(val, val);
    } else {
      const int current_min = this->getMin();
      const int new_min = std::min(current_min, val);
      this->stack_.emplace(val, new_min);
    }
  }

  void pop() {
    this->stack_.pop();
  }

  int top() {
    return this->stack_.top().first;
  }

  int getMin() {
    return this->stack_.top().second;
  }

 private:
  std::stack<std::pair<int, int>> stack_;
};

int main() {
  return 0;
}