力扣155题最全解法:如何实现支持常数时间获取最小值的最小栈(附详细图解和复杂度分析)

简介: 力扣155题最全解法:如何实现支持常数时间获取最小值的最小栈(附详细图解和复杂度分析)

❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容,和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣!

期待与您一起探索技术、持续学习、一步步打怪升级 欢迎订阅本专栏❤️❤️

在本篇文章中,我们将详细解读力扣第155题“最小栈”。通过学习本篇文章,读者将掌握如何设计一个支持常数时间复杂度检索最小元素的栈。我们将介绍多种解决方案,详细分析它们的优缺点,并提供相应的代码实现。每种方法都将配以详细的解释和图示,以便于理解。

问题描述

力扣第155题“最小栈”描述如下:

设计一个支持 pushpoptop 操作,并能在常数时间内检索到最小元素的栈。

  • push(x) – 将元素 x 推入栈中。
  • pop() – 删除栈顶的元素。
  • top() – 获取栈顶元素。
  • getMin() – 检索栈中的最小元素。

示例:

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

解题思路

  1. 初步分析
  • 我们需要设计一个栈,支持常见的栈操作(pushpoptop)和一个额外的操作(getMin)。
  • 关键在于如何在常数时间内实现 getMin 操作。
  1. 多种解法
  • 使用辅助栈法:利用两个栈,一个存储数据,一个存储最小值。
  • 使用栈中元素存储最小值法:在栈中每个元素同时存储当前元素和栈内最小值。

辅助栈法

解法思路

使用两个栈,一个栈 dataStack 用于存储所有的元素,另一个栈 minStack 用于存储当前最小值。

步骤
  1. push(x)
  • x 压入 dataStack
  • 如果 minStack 为空或者 x 小于等于 minStack 的栈顶元素,则将 x 压入 minStack
  1. pop()
  • dataStack 弹出栈顶元素。
  • 如果 dataStack 弹出的元素等于 minStack 的栈顶元素,则从 minStack 也弹出栈顶元素。
  1. top()
  • 返回 dataStack 的栈顶元素。
  1. getMin()
  • 返回 minStack 的栈顶元素。
代码实现
class MinStack:
    def __init__(self):
        self.dataStack = []
        self.minStack = []
    def push(self, x: int) -> None:
        self.dataStack.append(x)
        if not self.minStack or x <= self.minStack[-1]:
            self.minStack.append(x)
    def pop(self) -> None:
        if self.dataStack:
            top = self.dataStack.pop()
            if top == self.minStack[-1]:
                self.minStack.pop()
    def top(self) -> int:
        return self.dataStack[-1] if self.dataStack else None
    def getMin(self) -> int:
        return self.minStack[-1] if self.minStack else None
# 测试案例
minStack = MinStack()
minStack.push(-2)
minStack.push(0)
minStack.push(-3)
print(minStack.getMin())  # --> 返回 -3.
minStack.pop()
print(minStack.top())     # --> 返回 0.
print(minStack.getMin())  # --> 返回 -2.
图解
操作: push(-2)
dataStack: [-2]
minStack: [-2]
操作: push(0)
dataStack: [-2, 0]
minStack: [-2]
操作: push(-3)
dataStack: [-2, 0, -3]
minStack: [-2, -3]
操作: getMin()
返回: -3
操作: pop()
dataStack: [-2, 0]
minStack: [-2]
操作: top()
返回: 0
操作: getMin()
返回: -2

使用栈中元素存储最小值法

解法思路

在栈中每个元素同时存储当前元素和栈内最小值。

步骤
  1. push(x)
  • 如果栈为空,则将 (x, x) 压入栈,表示当前元素和当前最小值都是 x
  • 否则,将 (x, min(x, 当前最小值)) 压入栈。
  1. pop()
  • 从栈中弹出栈顶元素。
  1. top()
  • 返回栈顶元素的第一个值。
  1. getMin()
  • 返回栈顶元素的第二个值。
代码实现
class MinStack:
    def __init__(self):
        self.stack = []
    def push(self, x: int) -> None:
        if not self.stack:
            self.stack.append((x, x))
        else:
            current_min = self.stack[-1][1]
            self.stack.append((x, min(x, current_min)))
    def pop(self) -> None:
        if self.stack:
            self.stack.pop()
    def top(self) -> int:
        return self.stack[-1][0] if self.stack else None
    def getMin(self) -> int:
        return self.stack[-1][1] if self.stack else None
# 测试案例
minStack = MinStack()
minStack.push(-2)
minStack.push(0)
minStack.push(-3)
print(minStack.getMin())  # --> 返回 -3.
minStack.pop()
print(minStack.top())     # --> 返回 0.
print(minStack.getMin())  # --> 返回 -2.
图解
操作: push(-2)
stack: [(-2, -2)]
操作: push(0)
stack: [(-2, -2), (0, -2)]
操作: push(-3)
stack: [(-2, -2), (0, -2), (-3, -3)]
操作: getMin()
返回: -3
操作: pop()
stack: [(-2, -2), (0, -2)]
操作: top()
返回: 0
操作: getMin()
返回: -2

复杂度分析

  • 辅助栈法
  • 时间复杂度:
  • push 操作:O(1)
  • pop 操作:O(1)
  • top 操作:O(1)
  • getMin 操作:O(1)
  • 空间复杂度:O(N),其中 N 是栈中元素的数量。需要额外的栈来存储最小值。
  • 使用栈中元素存储最小值法
  • 时间复杂度:
  • push 操作:O(1)
  • pop 操作:O(1)
  • top 操作:O(1)
  • getMin 操作:O(1)
  • 空间复杂度:O(N),其中 N 是栈中元素的数量。栈中的每个元素存储两个值。

测试案例分析

  1. 测试案例 1
  • 操作:push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()
  • 输出:-3, 0, -2
  • 解释:通过连续的栈操作,可以验证 getMin 方法能够正确返回最小值。
  1. 测试案例 2
  • 操作:push(2), push(2), push(1), getMin(), pop(), getMin(), pop(), getMin()
  • 输出:1, 2, 2
  • 解释:通过重复的元素和变化的最小值,验证栈操作的正确性。

总结

本文详细解读了力扣第155题“最小栈”,通过辅助栈法和使用栈中元素存储最小值法两种不同的解法,帮助读者深入理解如何高效地实现一个支持常数时间内获取最小值的栈。希望读者通过本文的学习,能够在力扣刷题的过程中更加得心应手。

参考资料

  • 《算法导论》—— Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
  • 力扣官方题解

🌹🌹如果觉得这篇文对你有帮助的话,记得一键三连关注、赞👍🏻、收藏是对作者最大的鼓励,非常感谢 ❥(^_-)

❤️❤️关注公众号 数据分析螺丝钉 回复 学习资料 领取高价值免费学习资料❥(^_-)

欢迎关注微信公众号 数据分析螺丝钉

相关文章
|
21天前
|
存储 算法 测试技术
力扣经典150题第五十四题:最小栈
力扣经典150题第五十四题:最小栈
16 0
|
24天前
|
存储 算法 索引
力扣每日一题 6/24 模拟 数组 单调栈
力扣每日一题 6/24 模拟 数组 单调栈
9 0
|
12天前
|
Python
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
|
1月前
|
存储 算法 Python
二刷力扣--栈和队列
二刷力扣--栈和队列
|
1月前
|
存储 算法 数据可视化
力扣156题最全解法:如何上下翻转二叉树(递归与迭代方法详解,附图解)
力扣156题最全解法:如何上下翻转二叉树(递归与迭代方法详解,附图解)
|
1月前
|
存储 算法 数据可视化
深入解析力扣157题:用Read4高效读取N个字符(多种解法与详细图解)
深入解析力扣157题:用Read4高效读取N个字符(多种解法与详细图解)
|
1月前
|
存储 算法 数据可视化
深入解读力扣154题:寻找旋转排序数组中的最小值 II(多种方法及详细ASCII图解)
深入解读力扣154题:寻找旋转排序数组中的最小值 II(多种方法及详细ASCII图解)
|
1月前
|
存储 算法 数据可视化
|
1月前
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
|
1月前
|
容器
【LeetCode刷题】栈和队列题目练习~
【LeetCode刷题】栈和队列题目练习~