[LeetCode]Min Stack

题目描述:

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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

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

Pingbacks已关闭。

评论
  1. 翼灵贰駟 翼灵贰駟 发布于 2016年2月15日 15:28 #

    可以不用track 最小值出现的次数,而是采用和“新增值 < 最小值栈顶的值”相同的策略;
    当push(x)中的x与当前最小值相等时,把x也push进minStack中。

  2. 在线疯狂 在线疯狂 发布于 2016年2月16日 11:36 #

    感谢提醒!已将你的解法添加至博文的末尾:D

  3. Lost_in_ Lost_in_ 发布于 2016年4月18日 17:11 #

    超时的程序不是因为“leetcode OJ对于该题目的内存限制比较严苛”,而是push函数写错了...导致出错从而超时吧

  4. 在线疯狂 在线疯狂 发布于 2016年4月18日 20:21 #

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

  5. Lost_in_ Lost_in_ 发布于 2016年4月18日 23:01 #

    酱紫

张贴您的评论