题目描述：

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

题目大意：

设计一个栈，支持在常数时间内push，pop，top，和取最小值。

• push(x) -- 元素x压入栈
• pop() -- 弹出栈顶元素
• top() -- 获取栈顶元素
• getMin() -- 获取栈中的最小值

解题思路：

“双栈法”，栈stack存储当前的所有元素，minStack存储栈中的最小元素。

在操作元素栈stack的同时，维护最小值栈minStack。

对于push（x）操作：

stack.push( x )
minStack.push( min( minStack.top(), x ) )

注意事项（Tricks）：

leetcode OJ对于该题目的内存限制比较严苛，直接使用双栈法容易出现Memory Limit Exceeded（MLE）

可以使用下面的优化解决此问题，minStack存储元组（minVal, count），分别记录当前的最小值和出现次数。

如果新增元素x与最小值栈顶的minVal相同，则只更新count。

Python代码（Accepted）：

class MinStack:
  # @param x, an integer
  # @return an integer
  def __init__(self):
    self.stack = []
    self.minStack = [] #最小值栈 （最小值，出现次数）

  def push(self, x):
    self.stack.append(x)
    #如果 新增值x == 最小值栈顶的值
    if len(self.minStack) and x == self.minStack[-1][0]:
      #最小值栈顶元素次数+1
      self.minStack[-1] = (x, self.minStack[-1][1] + 1)
    #如果 最小值栈为空，或者新增值 < 最小值栈顶的值
    elif len(self.minStack) == 0 or x < self.minStack[-1][0]:
      #x入最小值栈
      self.minStack.append((x, 1))

  def pop(self):
    #如果 栈顶值 == 最小值栈顶值
    if self.top() == self.getMin():
      #如果 最小值栈顶元素次数 > 1
      if self.minStack[-1][1] > 1:
        #最小值栈顶元素次数 - 1
        self.minStack[-1] = (self.minStack[-1][0], self.minStack[-1][1] - 1)
      else:
        #最小值栈顶元素弹出
        self.minStack.pop()
    return self.stack.pop()

  def top(self):
    return self.stack[-1]

  def getMin(self):
    return self.minStack[-1][0]

下面的Python代码被LeetCode OJ判定为Memory Limit Exceeded

后来OJ放宽了内存限制，代码重新提交判定为Accepted（2016年4月18日更新）

class MinStack:
    # @param x, an integer
    # @return an integer
    def __init__(self):
        self.nodes = [] #元素栈
        self.minNodes = [] #最小值栈

    def push(self, x):
        self.nodes.append(x)
        if len(self.minNodes):
            x = min(self.minNodes[-1], x)
        self.minNodes.append(x)

    def pop(self):
        self.minNodes.pop()
        return self.nodes.pop()

    def top(self):
        return self.nodes[-1]

    def getMin(self):
        return self.minNodes[-1]

上述解法的优化：

特别感谢网友翼灵贰駟的指点，“可以不用track 最小值出现的次数，而是采用和“新增值 < 最小值栈顶的值”相同的策略；当push(x)中的x与当前最小值相等时，把x也push进minStack中。”

Python代码：

class MinStack:
  # @param x, an integer
  # @return an integer
  def __init__(self):
    self.stack = []
    self.minStack = [] #最小值栈 

  def push(self, x):
    self.stack.append(x)
    #如果 最小值栈为空，或者新增值 <= 最小值栈顶的值
    if len(self.minStack) == 0 or x <= self.minStack[-1]:
      #x入最小值栈
      self.minStack.append(x)

  def pop(self):
    #如果 栈顶值 == 最小值栈顶值
    if self.top() == self.getMin():
        #最小值栈顶元素弹出
        self.minStack.pop()
    return self.stack.pop()

  def top(self):
    return self.stack[-1]

  def getMin(self):
    return self.minStack[-1]

 

本文链接：http://bookshadow.com/weblog/2014/11/10/leetcode-min-stack/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码