【刷算法】包含min函数的栈

justCoding 发布于2019-08-22 18:21 / 2902人阅读

摘要：题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的函数。

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。

分析

该题目要求实现一个带有返回当前栈中最小元素功能的数据结构，首先会想到使用一个变量保存当前最小元素的下标，但是仔细一想，如果当前最小元素刚好在栈顶，此时执行pop操作，那么最小元素会被弹出，新的最小元素又上哪儿找呢？比较暴力的方法是出现这种情况时，再遍历一遍栈就能重新得到最小元素的下标，但是这么暴力操作就没意思了而且时间复杂度很好。

可以使用双栈来实现min功能，栈1常规保存元素，栈2保存此时此刻的栈中最小元素，比如说有元素进栈1，如果该元素小于栈2的栈顶元素，说明新的最小元素就是该进栈元素，否则，最小元素还是栈2的栈顶元素。

代码实现

var stack1 = [];
var stack2 = [];

function push(node)
{
    if(stack2.length === 0 && stack1.length === 0){
        stack1.push(node);
        stack2.push(node);
    } else{
        stack1.push(node);
        var stack2Top = stack2[stack2.length-1];
        if(node < stack2Top)
            stack2.push(node)
        else
            stack2.push(stack2Top);
    }
    
}
function pop()
{
    stack2.pop();
    return stack1.pop();
}
function top()
{
    return stack1[stack1.length-1];
}
function min()
{
    return stack2[stack2.length-1];
}

GPU云服务器云服务器包含文件函数 java的栈使用最新函数与算法 min

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

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

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

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

yanest 2019-08-23 15:10 评论0 收藏0
【刷算法】LeetCode.155-最小栈

摘要：题目描述设计一个支持，，操作，并能在常数时间内检索到最小元素的栈。删除栈顶的元素。检索栈中的最小元素。示例返回返回返回代码实现题目描述设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。 push(x) -- 将元素 x 推入栈中。 pop() -- 删除栈顶的元素。 top() -- 获取栈顶元素。 getMin() -- 检索栈中的最小元素。示例...

wing324 2019-08-23 11:31 评论0 收藏0
电机控制及调参

摘要：有刷电机结构简单开发久技术成熟响应速度快，起动扭矩大运行平稳，起制动效果好控制精度高使用成本低，维修方便而无刷电机由于无电刷，具有低干扰噪音低运转顺畅寿命长低维护成本等优点。电机控制方式力矩控制指定电机提供设置大小的力矩。 ...

不知名网友 2021-11-26 11:10 评论0 收藏0
⭐算法入门⭐《二叉树 - 二叉搜索树》简单05 —— LeetCode 897. 递增顺序搜索树

文章目录一、题目1、题目描述2、基础框架3、原题链接二、解题报告1、思路分析2、时间复杂度3、代码详解三、本题小知识四、加群须知一、题目 1、题目描述给你一棵二叉搜索树，请按中序遍历将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。样例输入： [5,3,6,2,4,null,8,1,null,null,nu...

Soarkey 2021-09-10 10:51 评论0 收藏0
＜LeetCode天梯＞Day031 验证二叉搜索树（递归+中序遍历） | 初级算法 | Pytho

摘要：有效二叉搜索树定义如下节点的左子树只包含小于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。而我们二叉搜索树保证了左子树的节点的值均小于根节点的值，根节点的值均小于右子树的值，因此中序遍历以后得到的序列一定是升序序列。 ...

Genng 2021-11-24 09:39 评论0 收藏0