LeetCode 刷题 (1)——栈的最小值

本贴最后更新于 1468 天前,其中的信息可能已经时过境迁

题目

  • 题目描述

    请设计一个栈,除了常规栈支持的 pop 与 push 函数以外,还支持 min 函数,该函数返回栈元素中的最小值。执行 push、pop 和 min 操作的时间复杂度必须为 O(1)。

  • 示例

    MinStack minStack = new MinStack();
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    minStack.getMin();   --> 返回 -3.
    minStack.pop();
    minStack.top();      --> 返回 0.
    minStack.getMin();   --> 返回 -2.
    

解题思路

可以定义两个栈,一个栈用于存放普通数据(数据栈),另一个栈用于记录当前栈中的最小值(最小值栈)。

栈中最小值只有在入栈或出栈后才会发生变化。当入栈时,只需比较入栈元素是否小于原来栈中最小值,若小于将该元素值保存到最小值栈中;若大于等于,则将原来栈中最小值再次保存到最小值栈中。当出栈时,依次将数据栈和最小值栈中元素出栈即可。

获取栈中最小值只需要返回最小值栈的栈顶元素即可。

具体代码

class MinStack:
    def __init__(self):
        """初始化"""
        self.items = []  # 数据栈
        self.min_items = []  # 最小值栈

    def push(self, x: int) -> None:
        """入栈"""
        self.items.append(x)  # 将元素压入数据栈
        if (self.min_items and x < self.min_items[-1]) or not self.min_items:  # 如果最小值栈中有元素,且入栈元素小于栈顶元素或最小值栈是空栈
            self.min_items.append(x)  # 将元素压入最小值栈
        else:  # 最小值未发生变化
            self.min_items.append(self.min_items[-1])

    def pop(self) -> None:
        """出栈"""
        self.items.pop()
        self.min_items.pop()

    def top(self) -> int:
        """"获取栈顶元素"""
        return self.items[-1]

    def get_min(self) -> int:
        """获取栈中最小值"""
        return self.min_items[-1]
  • Python

    Python 是一种面向对象、直译式电脑编程语言,具有近二十年的发展历史,成熟且稳定。它包含了一组完善而且容易理解的标准库,能够轻松完成很多常见的任务。它的语法简捷和清晰,尽量使用无异义的英语单词,与其它大多数程序设计语言使用大括号不一样,它使用缩进来定义语句块。

    534 引用 • 671 回帖
  • 数据结构
    87 引用 • 115 回帖 • 4 关注
  • 7 引用
  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    209 引用 • 72 回帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...
zyk
Once I never thought it would be like this,but in reality it is. 绍兴