文档章节

包含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

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周日乱弹 —— 小心着凉 @红薯

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @莱布妮子:5.33起,其声呜呜然,如怨如慕,如泣如诉。余音袅袅,不绝如缕。分享Arch Enemy的单曲《Bridge Of Destiny (2009)》 《Bridge Of...

小小编辑
今天
170
4
what f,,

anlve
今天
2
0
初级开发-编程题

` public static void main(String[] args) { System.out.println(changeStrToUpperCase("user_name_abc")); System.out.println(changeStrToLowerCase(changeStrToUpperCase("user_name_abc......

小池仔
今天
14
0
现场看路演了!

HiBlock
昨天
21
0
Rabbit MQ基本概念介绍

RabbitMQ介绍 • RabbitMQ是一个消息中间件,是一个很好用的消息队列框架。 • ConnectionFactory、Connection、Channel都是RabbitMQ对外提供的API中最基本的对象。Connection是RabbitMQ的s...

寰宇01
昨天
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部