剑指offer/LintCode12_最小栈

Betta 发布于2019-08-14 18:12 / 3098人阅读

摘要：剑指最小栈声明文章均为本人技术笔记，转载请注明出处解题思路实现功能实现一个最小栈，要求操作均为复杂度，解题思路用栈存储数据用最小栈存储中最小元素，保证栈顶元素与栈顶元素同步，表示此时最小值将与此时最小值比较，将更小的一方压栈，保证中栈顶始终

剑指offer/LintCode12_最小栈 声明

文章均为本人技术笔记，转载请注明出处https://segmentfault.com/u/yzwall

解题思路 实现功能：

实现一个最小栈，要求push(element),pop(),min()操作均为$O(1)$复杂度，

解题思路

用栈stack存储数据；

用最小栈minStack存储stack中最小元素，保证minStack栈顶元素与stack栈顶元素同步，minStack.peek()表示此时stack最小值

push(number)：minStack将number与此时最小值minStack.peek()比较，将更小的一方压栈，保证minStack中栈顶始终为最小值；

pop()：对stack进行pop()时，同时进行minStack.pop()，保证minStack与stack同步；

注意点

实现最大栈时，

push(number)操作只需push(Math.max(number, minStack.peek())，保证maxStack栈顶元素始终为最大值

pop操作时，maxStack与stack同时pop，保证同步；

题目链接

lintcode 12: http://www.lintcode.com/en/problem/min-stack/

Java代码

/**
 * 实现一个最小栈，要求push,pop,min操作均为O(1)复杂度
 * http://www.lintcode.com/en/problem/min-stack/
 * @author yzwall
 */
import java.util.ArrayDeque;

class MinStack {
    private ArrayDeque stack;
    private ArrayDeque minStack;
    
    MinStack() {
        this.stack = new ArrayDeque<>();
        this.minStack = new ArrayDeque<>();
    }
    
    public void push(int number) {
        stack.push(number);
        if (minStack.isEmpty()) {
            minStack.push(number);
        } else {
            // 实现最大栈时，只需push(Math.max(number, minStack.peek())
            minStack.push(Math.min(number, minStack.peek()));
        }
    }
    
    public int pop() {
        minStack.pop();
        return stack.pop();
    }
    
    public int min() {
        return minStack.peek();
    }
}

云服务器 GPU云服务器剑指 php栈顺序栈栈结构

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

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

剑指offer/LintCode40_用两个栈模拟队列

摘要：剑指用两个栈模拟队列声明文章均为本人技术笔记，转载请注明出处解题思路实现功能用两个栈模拟实现一个队列的，和操作解题思路假设有两个栈队列实现始终用入栈实现队列和实现由于依次出栈并压入中，恰好保证中顺序与模拟队列顺序一致，始终保证栈顶元素为模拟剑指offer/LintCode40_用两个栈模拟队列声明文章均为本人技术笔记，转载请注明出处https://segmentfault.com...

bawn 2019-08-14 18:12 评论0 收藏0
剑指offer/LintCode494_用两个队列实现一个栈

摘要：剑指用两个队列实现一个栈声明文章均为本人技术笔记，转载请注明出处解题思路实现功能用两个队列实现一个栈，实现，，和方法解题思路假设有队列和实现栈的操作实现栈操作始终用来入队实现实现栈的方法模拟栈的过程中，保证两个队列中始终有一个队列为空，另一剑指offer/LintCode494_用两个队列实现一个栈声明文章均为本人技术笔记，转载请注明出处https://segmentfault....

rose 2019-08-14 18:10 评论0 收藏0
【剑指offer】13.包含min函数的栈

摘要：题目定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的函数时间复杂度应为。这样最小值栈的栈顶永远是当前栈的最小值。题目定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。思路 1.定义两个栈，一个栈用于存储数据，另一个栈用于存储每次数据进栈时栈的最小值. 2.每次数据进栈时，将此数据和最小值栈的栈顶元素比较，将二者比...

yanest 2019-08-23 15:10 评论0 收藏0
【剑指offer】让抽象问题具体化

摘要：假设压入栈的所有数字均不相等。注意这两个序列的长度是相等的思路借助一个辅助栈来存储数据。当所有数据入栈完成，如果出栈顺序正确，那么辅助栈应该为空。若存在，左右子树，递归检测左右子树是否复合规范。 1.包含min函数的栈定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。思路 1.定义两个栈，一个栈用于存储数据，另一个栈用于存储每次数...

Keagan 2019-08-23 15:15 评论0 收藏0
从简历被拒到收割今日头条 offer，我用一年时间破茧成蝶！

摘要：正如我标题所说，简历被拒。看了我简历之后说头条竞争激烈，我背景不够，点到为止。。三准备面试其实从三月份投递简历开始准备面试到四月份收，也不过个月的时间，但这都是建立在我过去一年的积累啊。本文是无精疯同学投稿的面试经历关注微信公众号：进击的java程序员K，即可获取最新BAT面试资料一份在此感谢无精疯同学的分享目录：印象中的头条面试背景准备面试 ...

tracymac7 2019-08-15 17:57 评论0 收藏0