欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构与算法:第五周作业二:最小栈

程序员文章站 2022-06-03 13:45:54
...

题目描述

数据结构与算法:第五周作业二:最小栈
链接:https://leetcode-cn.com/problems/min-stack/

思路:

用一个辅助栈来记录最小值,最小值总是在栈顶,所以getMin(),返回-1的索引即可。
对于最小栈入栈的情况有三种:
1.最小栈为空,入栈。
2.当前元素<=栈顶元素,入栈。
3.当前元素>当前元素,出栈。

在pop()方法里,需要比较pop()的元素是否是最小栈的栈顶元素,如果是,那么最小栈的栈顶元素也需要被pop()。

代码

class MinStack:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.elem=[]
        self.min=[]
    def push(self, x: int) -> None:        
        self.elem.append(x)
        if not self.min or x<=self.min[-1]:
            self.min.append(x)
        def pop(self) -> None:
        if not self.elem:
            raise ValueError('in MinStack pop()')
        a=self.elem.pop()
        if a==self.min[-1]:
            self.min.pop()
    def top(self) -> int:
        if not self.elem:
            raise ValueError('in MinStack top()')
        return self.elem
    def getMin(self) -> int:
        return self.min[-1]       

数据结构与算法:第五周作业二:最小栈