当前位置:   article > 正文

求队列的最大值-辅助队列_获取队列最大值

获取队列最大值

请定义一个队列并实现函数 max_value 得到队列里的最大值,要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空,pop_front 和 max_value 需要返回 -1

与求栈的最大值的思想是一样的,唯一的区别是因为栈和队列的数据结构不同,所以最大值的位置有区别。
栈的最大值:https://blog.csdn.net/caihuanqia/article/details/105032483
下面是用列表实现了队列,没有直接用collection的deque。
都是用了辅助,区别是进栈的判断条件原因是先进后出和先进先出的区别。
1.栈(先进后出)的最大值:存储最大值的辅助栈,每次进入主栈的元素都与辅栈的头进行比较,如果大于头部,则进栈;每次主栈出栈的时候,如果与辅助栈的头部一致,则辅助栈也出栈。
2.队列(先进先出)的最大值:每次主队元素进队时,都把元素与辅助队列的队头进行比较,如果大于队头,则把队头元素删掉,循环,最后入队。主队出队时,与队尾元素进行比较,如果相等则出队。最大值存储在队头

队列先进先出,每次进队只保留最大值,因为前面先进来的走了,后面有最大值的还在。

def push_back(self, value):
    """
    :type value: int
    :rtype: None
    """
    if not value:
        return
    self.queue.append(value)

    while self.queue2 and value > self.queue2[-1]:
        self.queue2.pop(-1)
    self.queue2.append(value)
    # 重点!!!!!

def pop_front(self):
    """
    :rtype: int
    """
    if not self.queue:
        return -1
    if self.queue[0] == self.queue2[0]:
        self.queue2.pop(0)
    return self.queue.pop(0) 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/黑客灵魂/article/detail/960740
推荐阅读
相关标签
  

闽ICP备14008679号