资讯专栏INFORMATION COLUMN

【剑指offer】13.包含min函数的栈

yanest / 2392人阅读

摘要:题目定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的函数时间复杂度应为。这样最小值栈的栈顶永远是当前栈的最小值。

题目

定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。

思路

1.定义两个栈,一个栈用于存储数据,另一个栈用于存储每次数据进栈时栈的最小值.

2.每次数据进栈时,将此数据和最小值栈的栈顶元素比较,将二者比较的较小值再次存入最小值栈.

4.数据栈出栈,最小值栈也出栈。

3.这样最小值栈的栈顶永远是当前栈的最小值。

代码
var dataStack = [];
var minStack = [];
 
function push(node)
{
    dataStack.push(node);
    if(minStack.length === 0 ||  node < min()){
        minStack.push(node);
    }else{
        minStack.push(min());
    }
}
function pop()
{
    minStack.pop();
    return dataStack.pop();
}
function top()
{
    var length = dataStack.length;
    return length>0&&dataStack[length-1]
}
function min()
{
    var length = minStack.length;
    return length>0&&minStack[length-1]
}

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

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

相关文章

  • 剑指offer】让抽象问题具体化

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

    Keagan 评论0 收藏0
  • 剑指offer--JavaScript版

    摘要:剑指在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。例如输入前序遍历序列和中序遍历序列,则重建二叉树并返回。其中负数用补码表示。 本文为8月牛客网《剑指 offer》刷题做得,现整理出来作为参考。虽然是算法题,但本文用 JavaScript 编写,看了《剑指 offer》以后发现很多问题处理的过程并不是最好的,所以本文仅供参考。以前全部代码 A...

    MarvinZhang 评论0 收藏0
  • 剑指offer】8.斐波那契数列

    摘要:题目题目描述大家都知道斐波那契数列,现在要求输入一个整数,请你输出斐波那契数列的第项从开始,第项为。基本思路这道题在剑指中实际是当作递归的反例来说的。明显也符合斐波那契数列的规律矩形覆盖我们可以用的小矩形横着或者竖着去覆盖更大的矩形。 题目 题目描述大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。 基本思路 这道题在剑指offer中...

    sf_wangchong 评论0 收藏0
  • 剑指offer/LintCode12_最小栈

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

    Betta 评论0 收藏0
  • 剑指offer(javascript版)

    摘要:二维数组中的查找在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。例如输入前序遍历序列和中序遍历序列,则重建二叉树并返回。 1.二维数组中的查找 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数...

    imtianx 评论0 收藏0

发表评论

0条评论

yanest

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<