min stack

yy13818512006 发布于2019-08-16 10:33 / 757人阅读

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

public class MinStack {
    Stack stk;
    int min;
    
    /** initialize your data structure here. */
    public MinStack() {
        stk = new Stack();
        min = Integer.MAX_VALUE;
    }
    
    public void push(int x) {
        if(x <= min){
            stk.push(min);
            min = x;
        }
        stk.push(x);
    }
    
    public void pop() {
        if(stk.peek() == min){
            stk.pop();
            min = stk.pop();
        } else {
            stk.pop();
        }
    }
    
    public int top() {
        return stk.peek();
    }
    
    public int getMin() {
        return min;
    }
}

public class MinStack {
    ArrayDeque stack, min;
    
    public MinStack() {
        this.stack = new ArrayDeque();
        this.min = new ArrayDeque();
    }
    
    public void push(int x) {
        stack.push(x);
        if(min.isEmpty() || x <= min.peek()){
            min.push(x);
        }
    }
    
    public void pop() {
        if(stack.isEmpty()){
            return; 
        }
        if(min.peek().equals(stack.peek())){
            min.pop();
        }
        stack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return min.peek();
    }
}

GPU云服务器云服务器 Stacking Stacked Stacks Stack

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69993.html

[LintCode/LeetCode] Min Stack/Max Stack

Problem Implement a stack with min() function, which will return the smallest number in the stack. It should support push, pop and min operation all in O(1) cost. Example push(1)pop() // return 1pus...

GHOST_349178 2019-08-14 15:14 评论0 收藏0
每周一练之数据结构与算法（Stack）

摘要：二实现一个栈，并实现下面方法添加一个新元素到栈顶。移除栈顶的元素，同时返回被移除的元素。十进制转换为二进制请输入正确的数值方法简单实现下面这个方法，其实不太好，因为没有怎么用到这次要练习的栈方法，哈哈。最近公司内部在开始做前端技术的技术分享，每周一个主题的每周一练，以基础知识为主，感觉挺棒的，跟着团队的大佬们学习和复习一些知识，新人也可以多学习一些知识，也把团队内部学习氛围营造起来...

hzx 2019-08-23 16:55 评论0 收藏0
【刷算法】包含min函数的栈

摘要：题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的函数。题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。分析该题目要求实现一个带有返回当前栈中最小元素功能的数据结构，首先会想到使用一个变量保存当前最小元素的下标，但是仔细一想，如果当前最小元素刚好在栈顶，此时执行pop操作，那么最小元素会被弹出，新的最小元素又上哪儿找呢？比较暴力的方...

justCoding 2019-08-22 18:21 评论0 收藏0
我的面试准备过程--队列与栈(更新中)

摘要：和三个方法的时间复杂度必须为两种解法，解法一，将最小值存入自有的数据结构中，如下所示原本的值最小值解法二，用两个栈堆栈和队列统称线性表简单的线性结构数组和链表可以实现这两种数据结构堆栈基本理解 DFS 深度优先---按深度遍历递归转非递归队列基本理解 BFS 广度优先---按层序遍历出入栈的合法性模拟出入栈的过程，不是入栈，就是...

EastWoodYang 2019-08-16 10:38 评论0 收藏0
[Leetcode] Min Stack 最小栈

摘要：双栈法复杂度时间空间思路暴力的方法是遍历一遍栈得出最小值，这样不用任何空间。因为这个最小值的顺序也是先进后出，我们同样用一个栈来记录。这样主栈在时，如果该值小于等于副栈顶，就也进副栈中。当主栈时，如果出的元素是副栈栈顶的话，副栈也要。 Min Stack Design a stack that supports push, pop, top, and retrieving themin...

YorkChen 2019-08-14 12:31 评论0 收藏0