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