栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

剑指offer-用两个栈实现队列和包含min函数的栈

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

剑指offer-用两个栈实现队列和包含min函数的栈

Day01简单:剑指 Offer 09. 用两个栈实现队列
  • 题目:[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

  • 思路:两个栈,一个正常存入,另一个栈存储第一个栈弹出的元素。因为第一个栈弹出的元素必定是栈顶元素,存入到另一个栈中就到了栈底,这样在第二个栈就相当于是队列,弹出的元素是我们第一个存入的元素。

  • 代码:注意!不直接使用Stack,因为继承于Vector,加了锁效率低,而且Stack继承了Vector中无关的方法。

Day01简单:剑指 Offer 30. 包含min函数的栈
  • 题目:

  • 思路:同样是使用两个栈,一个是主栈,一个是最小栈。主栈正常存储元素,最小栈获取主栈的最小值。只不过这次,题目要求删除,增加操作的时间复杂度是O(1),那么就应该选择LinkedList实现类,因为链表增删改效率是O(1)。主栈进行正常的压入弹出,最小栈要注意:

  1. 初始化类的时候,往最小栈压入个int类型的最大值,方便后面操作。
  2. 往主栈压入元素时,最小栈要同时获取主栈中的最小值压入。这样的话,想一下栈顶元素是不是永远就是最小值了?那压入元素的时候怎么知道最小值呢?只要与当前栈顶元素比较就可以了,如果比栈顶元素小,那么压入的元素就是新的最小值,那么就把新元素压入栈顶;如果栈顶元素比压入的元素要小,那么栈顶元素依然是最小值,就继续压入栈顶的值。
  3. 弹出主栈栈顶元素时,要把最小栈的栈顶也弹出,因为最小栈与主栈栈顶元素是同时进来的,出去也要同时出去,才能保证最小值是最新的。
  4. 最后要获取最小值,就非常简单了,弹出最小栈的栈顶就可以了。
  • 代码:注意!不直接使用Stack,因为继承于Vector,加了锁效率低,而且Stack继承了Vector中无关的方法。

    package lapTop.Math;
    
    import java.util.Deque;
    import java.util.LinkedList;
    
    class MinStack {
        Deque mainStack;   //单独拎出来作为成员变量,所有方法共享。
        Deque minStack;
    
        
        public MinStack() {
            mainStack = new LinkedList<>();//用LinkedList实现类,因为题目要求增删改效率要O(1)
            minStack = new LinkedList<>();
        }
    
        public void push(int x) {
            //压入要同步,随时更新最小值
            mainStack.push(x);
            //因为栈顶永远是最小值,只需要用新来的和最小栈栈顶比较即可。
            minStack.push(Math.min(min(),x));
        }
    
        public void pop() {
            mainStack.pop();
            //要把最小栈的栈顶也弹出去,因为他们是同时进来的,同时出去才能更新最小值。
            minStack.pop();
        }
    
        public int top() {
            //如果这里用peek()的话可能会导致空指针异常。(IDEA的警告)
           return mainStack.element();
        }
    
        public int min() {
            //如果这里用peek()的话可能会导致空指针异常。(IDEA的警告)
            return minStack.element();
        }
    }
    
  • 感受:超,一点思路都没有,还得看官方题解。希望以后会更厉害。
    Stack.element();
    }
    }

    
    
  • 感受:超,一点思路都没有,还得看官方题解。希望以后会更厉害。

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/972781.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号