155 最小栈

题目信息

题目地址:https://leetcode-cn.com/problems/min-stack/

设计一个支持 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.

解法一:添加辅助栈

首先是具备栈的基本操作,除此之外添加了个获取最小元素的方法,也就是我们需要记录最小元素,但栈的元素变动有两种一种是入栈一种是出栈,这两种情况都会影响最小元素.所以我们没办法只用一个变量来记录最小值因为会回退,必须是容器存每个阶段最小值且变化逻辑与数据栈同步,这样一想的话就是再用一个栈呗.

如图:

这样的话,我们就是用另外一个栈记录最小值,并且可以跟随数据栈的变化回退或者添加,最终另外栈的顶部就是当前的最小值

下面我先手动实现个简单的栈再操作(因为是有两个栈都有基本操作,所以直接写在解题类里就会有重复,因此把栈的操作提出来),也可以就用java类库的栈

class MyStack {
    private int[] data;
    private int size = -1;
    public MyStack() {
      //data = new int[10000];
      data = new int[50];
    }
    public void push(int x) {
      // 是否需要扩容
      size++;
      if (size>data.length-1) {
        data=Arrays.copyOf(data, data.length*2);
      }  
      data[size] = x;
    }
    public void pop() {
      size--;
    }
    public int peek() {
      if(!isEmpty()){
        // 抛异常
      }
      return data[size];
    }
    public boolean isEmpty(){
      return size < 0;
    }
}

再用这个栈去是实现我们的最小栈:在入栈时判断当前元素是否比最小栈的栈顶要小,出栈时判断当前元素是否是最小栈的栈顶。

class MinStack {
    MyStack data;
    MyStack min;
    
    public MinStack() {
        data = new MyStack();
        min = new MyStack();
    }
    
    public void push(int x) {
        data.push(x);
        if(min.isEmpty() || x <= min.peek()){
            min.push(x);
        }
    }

    public void pop() {
        if(data.peek() == min.peek()){
            min.pop();
        }
        data.pop();
    }
    
    public int top() {
        return data.peek();
    }
    
    public int getMin() {
        return min.peek();
    }
}

时间复杂度:只有栈的操作,无论是弹出还是压栈都是O(1)的操作 空间复杂度:定义了两个栈需要去存储数据,最差情况是2n,因此空间复杂度为O(n)

解法二:封装元素数据

与解法一一个逻辑,既然两个栈是同步的关系,把辅助栈的数据放到到通一个栈也可以。每个元素是一个对象其中不仅包含当前数值也包含当前最小栈里最小值

class StackNode{
    private int value;
    private int min;
    public void setValue(int value){
        this.value = value;
    }
    public void setMin(int min){
        this.min = min;
    }
    public int getValue(){
        return value;
    }
    public int getMin(){
        return min;
    }
}

代码如下:

class MinStack {
    MyStack<StackNode> data;
    
    public MinStack() {
        data = new MyStack<StackNode>();
    }
    
    public void push(int x) {
        StackNode node = new StackNode();
        node.setValue(x);
        if(data.isEmpty() || x <= data.peek().getMin()){
            node.setMin(x);
        }else{
            node.setMin(data.peek().getMin());
        }
        data.push(node);
    }

    public void pop() {
        data.pop();
    }
    
    public int top() {
        return data.peek().getValue();
    }
    
    public int getMin() {
        return data.peek().getMin();
    }
}

判定点与解法一一样,只是放到了同一元素的第二属性。上面我们写的栈MyStack是写死的数据类型int数组,这里要全部换成StackNode不如就写个泛型的上面的解也是用的这个栈,如下:

class MyStack<T> {
    private T[] data;
    private int size = -1;
    public MyStack() {
      //data = new int[10000];
      data = (T[])new Object[50];
    }
    public void push(T x) {
      // 是否需要扩容
      size++;
      if (size>data.length-1) {
  data=Arrays.copyOf(data, data.length*2);
      }  
      data[size] = x;
    }
    public void pop() {
      size--;
    }
    public T peek() {
      if(!isEmpty()){
        // 抛异常
      }
      return data[size];
    }
    public boolean isEmpty(){
      return size < 0;
    }
}

时间复杂度和空间复杂度与解一一样分别是O(1)与O(n)

总结

总体上是比较简单可以快的找到思路的,同时也多熟悉熟悉栈的数据结构。这次动图是用adobe的an画的以后大概都会用这个做。设计问题的两题就完结了下篇开始初级的合集的数学问题

本文分享自微信公众号 - IT那个小笔记(Jasper-zh_blog),作者:木瓜煲鸡脚

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-03-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode:155 最小栈

    题目的意思是:在常数时间内获得栈中的最小值,意思是常数的话,代表一次就找到,一个栈不能解决用两个吧。(常数时间内O(1)),使用两个栈,一个普通栈,一个最小元素...

    贵哥的编程之路
  • LeetCode 155. 最小栈

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

    freesan44
  • 【LeetCode】155. 最小栈

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

    韩旭051
  • Leetcode No.155 最小栈

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

    week
  • LeetCode 155:最小栈 Min Stack

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

    爱写bug
  • 【leetcode系列】 155.最小栈

    符合直觉的方法是,每次对栈进行修改操作(push和pop)的时候更新最小值。然后getMin只需要返回我们计算的最小值即可, top也是直接返回栈顶元素即可。这...

    lucifer210
  • ​LeetCode刷题实战155:最小栈

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • 栈问题-LeetCode 155、42(最小栈问题)

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

    算法工程师之路
  • 【设计数据结构】面试官:请设计一个「最小栈」...

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

    宫水三叶的刷题日记
  • 最小栈

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

    _kyle
  • leetcode栈之最小栈

    这里再push的时候,计算了min值,同时再min值有更新的时候,先push了上一个min值,最后再push当前的min值;在pop的时候,判断是否等于min值...

    codecraft
  • leetcode栈之最小栈

    这里再push的时候,计算了min值,同时再min值有更新的时候,先push了上一个min值,最后再push当前的min值;在pop的时候,判断是否等于min值...

    codecraft
  • 【LeetCode】最小栈

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

    Delevin
  • Swift 最小栈 - LeetCode

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

    韦弦zhy
  • 包含min函数的栈

    LeetCode 155. Min Stack 设计一个栈,支持如下操作,这些操作的算法复杂度需要是常数级,O(1) 1.push(x) : 将元素x压入...

    小飞侠xp
  • Day5-线性表-栈-最小栈问题

    而且今天本来按照之前说的,应该更两篇的,但是今天只有一篇盒饭,还不是因为最近需求排的紧,加班加点干活,大哥们见谅

    BUPTrenyi
  • 每日一刷:最小栈

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

    乐心湖
  • 漫画:最小栈问题

    设一个变量int min = -1; 当一个元素进入栈时,把最小值的下标记录成0,后面进来的数和stack[min]做比较,如果大于等于当前的最小值,那就不做变...

    CSDN技术头条
  • LeetCode,Go 实现最小栈

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

    微客鸟窝

扫码关注云+社区

领取腾讯云代金券