希望對(duì)你有幫助呀！！💜💜 如有更好理解的思路，歡迎大家留言補(bǔ)充 ~ 一起加油叭 💦
歡迎關(guān)注、訂閱專欄 【力扣詳解】謝謝你的支持！

? 題目描述：

• 設(shè)計(jì)一個(gè)支持 push ，pop ，top 操作，并能在 常數(shù)時(shí)間內(nèi) ? 檢索到最小元素的棧。

• 實(shí)現(xiàn) MinStack 類:

  • MinStack()
    • 初始化堆棧對(duì)象
  • void push(int val)
    • 將元素val推入堆棧
  • void pop()
    • 刪除堆棧頂部的元素
  • int top()
    • 獲取堆棧頂部的元素
  • int getMin() 【 👉 唯一與普通棧不同的點(diǎn)】
    • 獲取堆棧中的最小元素

🔥 思路：用空間換時(shí)間，設(shè)計(jì)輔助棧來存儲(chǔ)棧內(nèi)每個(gè)元素為棧頂元素時(shí)對(duì)應(yīng)的棧的最小元素 👉 如下圖所示

• 基于這樣的設(shè)計(jì)， int getMin() 獲取堆棧中的最小元素時(shí)，僅需要返回輔助棧的棧頂元素即可
• 注意：對(duì)于普通棧，如果要檢索到最小元素，復(fù)雜度為 O(n)，不符合時(shí)間復(fù)雜度 ? 要求

參考如上思路，給出構(gòu)建輔助棧 min_stack 的詳細(xì)步驟如下：

• 回顧：輔助棧是用來存儲(chǔ)棧內(nèi)每個(gè)元素為棧頂元素時(shí)對(duì)應(yīng)的 ”棧的最小元素“ 的
• 新入棧元素 val 對(duì)應(yīng)的 “棧的最小元素” 應(yīng)該為 a. 舊棧頂元素對(duì)應(yīng)的 “棧的最小元素” 和 b. 新元素 val 的最小值
  • a. 舊棧頂元素對(duì)應(yīng)的 “棧的最小元素” 對(duì)應(yīng) self.min_stack[-1]，所以需要新入棧 min_stack 的值應(yīng)為 min(val, self.min_stack[-1])
  • 對(duì)應(yīng)部分在下方代碼中用 “## 核心代碼行” 標(biāo)識(shí)

class MinStack:def __init__(self):self.stack = [None]self.min_stack = [math.inf]  ## 可以發(fā)現(xiàn)，輔助棧是向棧頂方向遞減的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]

希望對(duì)你有幫助呀！！💜💜 如有更好理解的思路，歡迎大家留言補(bǔ)充 ~ 一起加油叭 💦
🔥 LeetCode 熱題 HOT 100