LeetCode 热题 HOT 100 （015/100）【宇宙最简单版】

希望对你有帮助呀！！💜💜 如有更好理解的思路，欢迎大家留言补充 ~ 一起加油叭 💦
欢迎关注、订阅专栏 【力扣详解】谢谢你的支持！

⭐ 题目描述：

• 设计一个支持 push ，pop ，top 操作，并能在 常数时间内 ⏳ 检索到最小元素的栈。

• 实现 MinStack 类:

  • MinStack()
    • 初始化堆栈对象
  • void push(int val)
    • 将元素val推入堆栈
  • void pop()
    • 删除堆栈顶部的元素
  • int top()
    • 获取堆栈顶部的元素
  • int getMin() 【 👉 唯一与普通栈不同的点】
    • 获取堆栈中的最小元素

🔥 思路：用空间换时间，设计辅助栈来存储栈内每个元素为栈顶元素时对应的栈的最小元素 👉 如下图所示

• 基于这样的设计， int getMin() 获取堆栈中的最小元素时，仅需要返回辅助栈的栈顶元素即可
• 注意：对于普通栈，如果要检索到最小元素，复杂度为 O(n)，不符合时间复杂度 ⏳ 要求

参考如上思路，给出构建辅助栈 min_stack 的详细步骤如下：

• 回顾：辅助栈是用来存储栈内每个元素为栈顶元素时对应的 ”栈的最小元素“ 的
• 新入栈元素 val 对应的 “栈的最小元素” 应该为 a. 旧栈顶元素对应的 “栈的最小元素” 和 b. 新元素 val 的最小值
  • a. 旧栈顶元素对应的 “栈的最小元素” 对应 self.min_stack[-1]，所以需要新入栈 min_stack 的值应为 min(val, self.min_stack[-1])
  • 对应部分在下方代码中用 “## 核心代码行” 标识

class MinStack:def __init__(self):self.stack = [None]self.min_stack = [math.inf]  ## 可以发现，辅助栈是向栈顶方向递减的def push(self, val: int) -> None:self.stack.append(val)self.min_stack.append(min(val, self.min_stack[-1]))  ## 核心代码行def pop(self) -> None:self.stack.pop()self.min_stack.pop()def top(self) -> int:return self.stack[-1]def getMin(self) -> int:return self.min_stack[-1]

希望对你有帮助呀！！💜💜 如有更好理解的思路，欢迎大家留言补充 ~ 一起加油叭 💦
🔥 LeetCode 热题 HOT 100