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

? 題目描述：

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

• 實現(xiàn) MinStack 類:

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

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

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

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

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

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]

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