155. 最小栈-白红宇的个人博客

155. 最小栈

发布日期：2021-05-06 11:08:49 浏览次数：25 分类：精选文章

本文共 1025 字，大约阅读时间需要 3 分钟。

MinStack是一种基于栈结构的数据结构，旨在高效实现数据的最小值查询和维护。该数据结构通过维护两个辅助栈来实现，其核心思想与传统的"栈最小值"问题类似，但具体实现方式有所优化。

核心数据结构

主栈（self.stack）：负责存储所有操作后的数据值。

辅助栈（self.min_val）：用于记录当前有效的最小值，避免频繁遍历主栈查询。

核心操作

初始化：

class MinStack(object):    def __init__(self):        self.stack = []        self.min_val = []

stack 用于存储所有插入的值。

min_val 用于存储当前有效的最小值序列。

插入值：

def push(self, val):    if not self.min_val or self.min_val[-1] >= val:        self.min_val.append(val)    else:        self.min_val.append(self.min_val[-1])    self.stack.append(val)

当插入的值 val 小于或等于当前最小值时，直接将 val 添加至 min_val。

否则，将当前最小值再次添加至 min_val。

同时，将 val 加入主栈 stack。

弹出值：

def pop(self):    self.min_val.pop()    return self.stack.pop()

弹出当前最小值记录。

同时移除主栈的最后一个元素。

查看顶部：

def top(self):    return self.stack[-1]

返回主栈的顶部元素。

获取最小值：

def getMin(self):    return self.min_val[-1]

直接返回当前最小值。

优势分析

时间复杂度：每次插入和弹出操作均为 O(1)，查询最小值为 O(1)。

空间复杂度：辅助栈 min_val 的空间复杂度为 O(N)，主栈 stack 的空间复杂度为 O(N)。

应用场景

该数据结构适用于需要频繁查询最小值但不希望每次查询都遍历整个数据集的场景，如网络流量监控、数据缓存等。

通过上述设计，MinStack 不仅实现了高效的值插入与弹出功能，还保证了对当前最小值的快速访问，充分发挥了栈数据结构的优势。

上一篇：SQL(六)

下一篇：17. 电话号码的字母组合

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！