Powered by:NEFU AB-IN

Link

41. 包含min函数的栈

• 题意

  设计一个支持push，pop，top等操作并且可以在O(1)时间内检索出最小元素的堆栈。
  push(x)–将元素x插入栈中
  pop()–移除栈顶元素
  top()–得到栈顶元素
  getMin()–得到栈中最小元素

• 思路

  创建两个栈

  • a栈代表原栈
  • b栈代表最小元素栈，即第i个元素存的是a栈前i个元素的最小值

  所以b的每个新元素，就从a的新元素和b的栈顶中，取最小值即可

• 代码

  class MinStack(object):
  
      def __init__(self):
          self.a = []
          self.b = []
          """
          initialize your data structure here.
          """
          
  
      def push(self, x):
          self.a.append(x)
          if not self.b:
              self.b.append(x)
          else:
              self.b.append(min(self.b[-1], x))
          """
          :type x: int
          :rtype: void
          """
          
  
      def pop(self):
          self.a.pop()
          self.b.pop()
          """
          :rtype: void
          """
          
  
      def top(self):
          return self.a[-1]
          """
          :rtype: int
          """
          
  
      def getMin(self):
          return self.b[-1]
          """
          :rtype: int
          """
          
  
  
  # Your MinStack object will be instantiated and called as such:
  # obj = MinStack()
  # obj.push(x)
  # obj.pop()
  # param_3 = obj.top()
  # param_4 = obj.getMin()