剑指 Offer 59 - II. 队列的最大值

秒速五厘米 2022-12-07 15:12 84阅读 0赞

[剑指 Offer 59 - II. 队列的最大值][Offer 59 - II.]

请定义一个队列并实现函数 max\_value 得到队列里的最大值，要求函数max\_value、push\_back 和 pop\_front 的均摊时间复杂度都是O(1)。

若队列为空，pop\_front 和 max\_value 需要返回 -1

**示例 1：**

输入: 
    ["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
    [[],[1],[2],[],[],[]]
    输出: [null,null,null,2,1,2]

**示例 2：**

输入: 
    ["MaxQueue","pop_front","max_value"]
    [[],[],[]]
    输出: [null,-1,-1]

解法1:  （不知道 这种方法  均摊时间复杂度是否为O(1)， 哪位大佬帮忙 指教下）

class MaxQueue:
    
        def __init__(self):
            self.queue = []
        def max_value(self) -> int:
            if self.queue:
                return max(self.queue)  # 寻找最大值
            return -1
        def push_back(self, value: int) -> None:
            # print(value)
            self.queue.append(value)
    
        def pop_front(self) -> int:
            if self.queue:
                pop_value = self.queue[0]
                self.queue = self.queue[1:]
                return pop_value
            return -1

[Offer 59 - II.]: https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/

发表评论取消回复

表情：

评论列表（有 0 条评论，84人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指Offer系列（java版，详细解析）59.队列的最大值

题目描述 [剑指 Offer 59 - I. 滑动窗口的最大值][Offer 59 - I.] 难度困难240收藏分享切换为英文接收动态反馈给定一个数组 `nu

偏执的太偏执、/ 2023年01月13日 10:21/ 0 赞/ 85 阅读

相关剑指 Offer 59 - II. 队列的最大值

[剑指 Offer 59 - II. 队列的最大值][Offer 59 - II.] 请定义一个队列并实现函数 max\_value 得到队列里的最大值，要求函数max\_v

秒速五厘米/ 2022年12月07日 15:12/ 0 赞/ 85 阅读

相关【剑指Offer】59.2 队列的最大值

[力扣][Link 1] 题目请定义一个队列并实现函数 max\_value 得到队列里的最大值，要求函数max\_value、push\_back 和 pop\_f

冷不防/ 2022年12月02日 13:43/ 0 赞/ 98 阅读

相关【剑指Offer】59. 1滑动窗口的最大值

[NowCoder][] 题目描述给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组 \{2, 3, 4, 2, 6, 2, 5,

蔚落/ 2022年12月02日 13:39/ 0 赞/ 111 阅读

相关剑指 Offer 59 - II. 队列的最大值（单调队列）

请定义一个队列并实现函数 max\_value 得到队列里的最大值，要求函数max\_value、push\_back 和 pop\_front 的均摊时间复杂度都是O(1)。

待我称王封你为后i/ 2022年11月25日 04:14/ 0 赞/ 83 阅读

相关剑指 Offer 59 - II. 队列的最大值

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

浅浅的花香味﹌/ 2022年10月27日 01:41/ 0 赞/ 104 阅读

相关剑指 Offer 59 - I. 滑动窗口的最大值

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

系统管理员/ 2022年10月27日 01:39/ 0 赞/ 109 阅读

相关【leetcode】剑指 Offer 59 - I. 滑动窗口的最大值

剑指 Offer 11. 旋转数组的最小数字题目难度：困难方法一：双端队列 > 链接：[https://leetcode-cn.com/problems

系统管理员/ 2022年10月17日 04:14/ 0 赞/ 101 阅读

相关【剑指offer】面试题59（1）：滑动窗口的最大值

题目给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如：如果输入数组\{2,3,4,2,6,2,5,1\}及滑动窗口的大小3，那么一共存在6

左手的ㄟ右手/ 2022年06月11日 09:53/ 0 赞/ 133 阅读

相关 [剑指offer题解][Java]队列的最大值/滑动窗口的最大值

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

缺乏、安全感/ 2022年05月13日 12:44/ 0 赞/ 159 阅读