Q155 Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.
Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.
解题思路:

此题为栈的基本操作,加了一个在 O(1) 的时间返回最小值的功能。

具体做法先在初始化的时候定义一个栈。在每次压栈(push)的过程中,先取出最小值(getMin)与当前压入栈的值比较,更新当前最小值。最后,把当前压入值和当前最小值都压入栈中,方便在得到最小值(getMin)的时候直接取出即可。

注意点:

pop() 之前要确保栈不能为空;top() 是取出栈顶值,而不是删除栈顶元素。

Python实现:
class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []  # 定义一个栈

    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        curMin = self.getMin()  # 取出最小值
        if curMin == None or x < curMin:
            curMin = x
        self.stack.append((x, curMin))   # 同时保存最小值
        
    def pop(self):
        """
        :rtype: void
        """
        if len(self.stack) != 0:  # 判断栈是否为空
            self.stack.pop()[0]

    def top(self):
        """
        :rtype: int
        """
        if len(self.stack) == 0:  # 判断栈是否为空
            return None
        return self.stack[-1][0]

    def getMin(self):
        """
        :rtype: int
        """
        if len(self.stack) == 0:
            return None
        return self.stack[-1][1]  # 返回最小值
        


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

obj = MinStack()
obj.push(-2)
obj.push(1)
obj.push(-3)
print(obj.getMin())  # -3
obj.pop()
print(obj.top())  # 1
print(obj.getMin())  # -2

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

cf314E. Sereja and Squares(dp)

给你一个擦去了部分左括号和全部右括号的括号序列,括号有25种,用除x之外的小写字母a~z表示。求有多少种合法的括号序列。答案对4294967296取模。 合法序...

1547
来自专栏静默虚空的博客

排序四 希尔排序

要点 希尔(Shell)排序又称为缩小增量排序,它是一种插入排序。它是直接插入排序算法的一种威力加强版。 该方法因DL.Shell于1959年提出而得名。 希尔...

2579
来自专栏CDA数据分析师

学会这8个(组)excel函数,轻松解决工作中80%的难题

文 | 兰色幻想-赵志东 函数是excel中最重要的分析工具,面对400多个excel函数新手应该从哪里入手呢?下面是实际工作中最常用的8个(组)函数,学会后工...

1967
来自专栏青青天空树

小白详细讲解快速幂--杭电oj2035-A^B

输入数据包含多个测试实例,每个实例占一行,由两个正整数A和B组成(1<=A,B<=10000),如果A=0, B=0,则表示输入数据的结束,不做处理。

1433
来自专栏数据结构与算法

P1168 中位数

题目描述 给出一个长度为N的非负整数序列A[i],对于所有 ]的中位数。 个数的中位数。 输入输出格式 输入格式: 输入文件median.in的第1...

31811
来自专栏数据结构与算法

BZOJ4653: [Noi2016]区间(线段树 双指针)

按照dls的说法,一般这一类的题有两种思路,一种是枚举一个点$M$,然后check它能否成为答案。但是对于此题来说好像不好搞

1072
来自专栏前端杂谈

前端算法-基本排序算法比较

36913
来自专栏编程

Python内置函数int高级用法

int()函数常用来把其他类型转换为整数,例如: >>>int(3.2) 3 >>>int(1/3) 其实,int是Python内置类型之一,之所以能够当作函数...

2609
来自专栏JavaEdge

设计模式实战 - 解释器模式(Interpreter Pattern)

● 公式可以运行时编辑,并且符合正常算术书写方式,例如a+b-c ● 高扩展性,未来增加指数、开方、极限、求导等运算符号时较少改动 ● 效率可以不用考虑,晚...

1052
来自专栏python3

习题4:变量和命名

"_"下划线这个符号在变量里通常被用作假象的空格,用来隔开单词,切记千万不要用"-"这个符号来连接单词

572

扫码关注云+社区

领取腾讯云代金券