美文网首页
栈-E155-最小栈

栈-E155-最小栈

作者: 三次元蚂蚁 | 来源:发表于2019-03-23 15:03 被阅读0次

题目

  • 概述:设计一个栈,除了支持栈的核心操作push(x),pop(),top()外,还支持在常数时间内找到栈中最小的元素
  1. push(x):将x入栈
  2. pop():将栈顶元素出栈
  3. top():获取栈顶元素
  4. getMin():取得栈中最小元素

出处:https://leetcode-cn.com/problems/min-stack/

思路

  • 为栈中每一个结点添加一个属性minValue,标志以该结点为栈顶的栈的最小元素

  • 每次入栈的结点的minValue为该结点的值本身

  • 入栈时比较入栈的结点和栈顶结点的minValue,若入栈的结点的minValue大于栈顶结点的minValue,则更新入栈的结点的minValue为栈顶结点的minValue

注意:如果栈中没有元素,则直接入栈即可

  • 栈中最小元素为栈顶元素的minValue

代码

class MinStack {
    private Node dummyHead;
    
    /** initialize your data structure here. */
    public MinStack() {
        dummyHead = new Node(0);
    }
    
    public void push(int x) {
        Node newNode = new Node(x);
        if (dummyHead.next != null) {
            if (newNode.minValue > getMin()) {
                newNode.minValue = getMin();
            }
        }
        newNode.next = dummyHead.next;
        dummyHead.next = newNode;
    }
    
    public void pop() {
        Node delNode = dummyHead.next;
        dummyHead.next = delNode.next;
        delNode.next = null;
        delNode = null;
    }
    
    public int top() {
        return dummyHead.next.value;
    }
    
    public int getMin() {
        return dummyHead.next.minValue;
    }
    
    class Node {
        int value;
        Node next;
        int minValue;
        public Node(int value) {
            this.value = value;
            this.next = null;
            this.minValue = value;
        }
    }
}

相关文章

  • 栈-E155-最小栈

    题目 概述:设计一个栈,除了支持栈的核心操作push(x),pop(),top()外,还支持在常数时间内找到栈中最...

  • LeetCode-155-最小栈

    LeetCode-155-最小栈 155. 最小栈[https://leetcode-cn.com/problem...

  • 栈--最小栈问题

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

  • 栈和队列

    1、栈 栈是一种先进先出的数据结构。栈顶进栈,栈顶出栈。 数据结构 栈的初始化 进栈 出栈 栈的最小值 2、队列 ...

  • 栈系列之-获取最小值

    一、栈获取最小值算法概述 获取栈的最小值算法:可以动态的获取一个栈中元素的最小值,动态的意思是,当该栈发生push...

  • Stack

    最大栈,最小栈,要求能实时返回栈中最大值或者最小值的 就需要两个栈,一个栈是正常操作,另一个栈专门记录到此数为止的...

  • 最小栈

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

  • 最小栈

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

  • 最小栈

    https://leetcode-cn.com/explore/interview/card/bytedance/...

  • 最小栈

    题目描述 https://leetcode-cn.com/problems/min-stack/ 解 思路 用一个...

网友评论

      本文标题:栈-E155-最小栈

      本文链接:https://www.haomeiwen.com/subject/bgjsvqtx.html