文档章节

包含min函数的栈

F
 FollowMee
发布于 2017/06/24 20:36
字数 291
阅读 0
收藏 0

包含min函数的栈

题目内容:定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数

解法:对象中持有两个list,一个用来模拟栈结构保存数据,另外一个保存最小值

  • 常规写法
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.s1 = []
        self.s2 = []
        
    def push(self, node):
        # write code here
        if not self.s1 and not self.s2: #栈空间为空时插入
            self.s1.append(node)
            self.s2.append(node)
        else:
            self.s1.append(node)
            if node < self.s2[-1]: #插入值小于最小栈顶点值时
                self.s2.append(node)
            else:
                self.s2.append(self.s2[-1]) #插入值大于最小栈顶点值时
    def pop(self):
        # write code here
        if self.s1 and self.s2:
            self.s2.pop()
            return self.s1.pop()
        return None
    def top(self):
        # write code here
        if self.s1:
            return self.s1[-1]
        return None
    def min(self):
        # write code here
        if self.s2:
            return self.s2[-1]
        return None

注意:边界条件

  • Pythonic

直接使用一个list来模拟栈,最小值使用内置min函数得到

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.s = []
    def push(self, node):
        # write code here
        self.s.append(node)
    def pop(self):
        # write code here
        if self.s:
            return self.s.pop()
        return None
    def top(self):
        # write code here
        if self.s:
            return self.s[-1]
        return None
    def min(self):
        # write code here
        if self.s:
            return min(self.s)
        return None

 

© 著作权归作者所有

共有 人打赏支持
F
粉丝 1
博文 8
码字总数 2003
作品 0
私信 提问
[算法总结] 3 道题搞定 BAT 面试——堆栈和队列

本文首发于我的个人博客:尾尾部落 0. 基础概念 栈:后进先出(LIFO) 队列:先进先出(FIFO) 栈的 java 实现 2. 队列的 java 实现 1. 用两个栈实现队列 剑指offer:用两个栈实现队列 Leet...

繁著
09/04
0
0
面试题_设计包含 min函数的栈

设计包含 min函数的栈() 定义栈的数据结构,要求添加一个 minminmin函数,能够得到栈的最小元素。 要求函数 min、push以及 pop 的时间复杂度都是 O(1)。 #include <iostream>using namespa...

梦想游戏人
2015/07/01
0
0
C++学习笔记(六)

题目:栈的压入与弹出序列 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序,假设压入栈的所有数字均不相等。例如:序列1、2、3、4、5是某栈的压栈序列...

初雪之音
2016/01/21
18
0
包含min函数的栈

题目:定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中,调用min、push及pop的时间复杂度都是O(1)。 解题思路:把每次的最小元素都保存起来放到另外一个辅助...

许大树
2017/10/19
0
0
算法3-设计包含min函数的栈

题目:定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。 要求函数min、push以及pop的时间复杂度都是O(1)。 思路:使用一个辅助栈来保存最小元素,这个解法简单不失优雅。设该...

kuanshang
2014/03/06
0
0

没有更多内容

加载失败,请刷新页面

加载更多

新手也能看懂,消息队列其实很简单

该文已加入开源项目:JavaGuide(一份涵盖大部分Java程序员所需要掌握的核心知识的文档类项目,Star 数接近 16k)。地址:https://github.com/Snailclimb/JavaGuide. 本文内容思维导图: 消息...

阿里云官方博客
15分钟前
0
0
如何在Chrome浏览器中启动deviceready事件(尝试调试phonegap项目)?

我正在开发PhoneGap应用程序,我希望能够在Chrome中调试它,而不是在电话上调试。但是,我在onGetReady()函数中初始化我的代码,该函数在PhoneGap触发“deviceready”事件时触发。由于Chr...

kisshua
今天
9
0
nginx中部署vue打包后的静态文件

如何在nginx中部署静态资源就不描述了, 请看我的这篇博客 将vue脚手架项目打包后的静态文件放到nginx上, 发现有个问题, 即url上有#, 怎么去掉这个#呢. 1 项目中router的mode 路由的mode要为h...

克虏伯
今天
13
0
JS容易理解错误的地方

在这端代码执行的末尾,你会不会hi变量回事函数中的hi了?你会不会认为这不是按引用传递了? 对值传递和引用传递产生质疑了? 1 var hi = {};2 function sayHello(hi) { ...

器石_
今天
9
0
Java开发学习--MongoDB

之前只学过sql,第一次使用非关系型数据库。以前对于关系型数据库与非关系型数据库的概念很模糊,通过这次的学习对这两者有了一个清晰的概念。 主键 在MongoDB中,主键名叫"_id",如果在生成...

微笑向暖wx
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部