【Leetcode解題】155. Min Stack

題目

• 題目連結
• 目標函式 :
  • void push(int val)
  • void pop()
  • int top()
  • int getMin()

解題概念

• 題意 : 需要實作 MinStack class，除了基本 Stack 的功能外，也須包含 getMin() 之功能
  • MinStack() : 對 MinStack 物件進行初始化
  • void push(int val) : 對 Stack Push 一整數
  • void pop() : 對 Stack Pop 一整數
  • int top() : 回傳 Stack 最上層之整數
  • int getMin() : 回傳 Stack 中的最小值

我的寫法

• 想法 :
  • 用 list 去實作 Stack
  • 用 index 來儲存當前最上層整數的索引值
  • getMin() 使用 sorted 來排序 list 後再回傳第一個整數
• 程式碼 :

  class MinStack(object):
  
      def __init__(self):
          self.stack = []
          self.index = -1 
  
      def push(self, val):
          """
          :type val: int
          :rtype: None
          """
          self.stack.append(val)
          self.index += 1
  
          
  
      def pop(self):
          """
          :rtype: None
          """
          self.stack.pop(self.index)
          self.index -= 1
  
  
      def top(self):
          """
          :rtype: int
          """
  
  
          return self.stack[self.index]
          
  
      def getMin(self):
          """
          :rtype: int
          """
          min_item = sorted(self.stack)[0] 
  
  
          return min_item

• 成效 :
  • Time Complexity : $O(1)$ / $O(n)$
  • Runtime: 387 ms (faster than 7.44%)
  • Memory Usage: 16.9 MB (more than 53.79%)

解答 or 其他優秀寫法

• 想法 :

  • 首先，使用 Linked List 去實作 Stack 的方式作為基底
  • 在 Node 設計方面，新增一格 min : 含該節點以下之 Stack 的最小值
  • Push() 需要特別處理，操作請見下圖

    

• 程式碼 :

  class MinStack(object):
  
      class Node:
          def __init__(self, val, min, next = None):
              self.val = val
              self.min = min
              self.next = next
  
      def __init__(self):
          self.head = None
  
      def push(self, val):
          """
          :type val: int
          :rtype: None
          """
          if not self.head: # Case 1
              self.head = self.Node(val = val, min = val)
          else: # Case 2
              self.head = self.Node(val = val, min = min(val, self.head.min), next =  self.head)
  
      def pop(self):
          """
          :rtype: None
          """
          self.head = self.head.next
  
  
      def top(self):
          """
          :rtype: int
          """
          return self.head.val
          
  
      def getMin(self):
          """
          :rtype: int
          """
          return self.head.min

• 成效 :

  • Time Complexity : $O(1)$
  • Runtime: 54 ms (faster than 24.69%)
  • Memory Usage: 19.4 MB (more than 8.9%)