LeetCode刷题--点滴记录014

以你之姓@ 2023-09-28 09:58 66阅读 0赞

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

**要求**

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

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

**解题**

#### C++版本 ####

#include <iostream>
    using namespace std;
    #include <queue>
    
    class MaxQueue {
        
        queue<int> que; // 队列queue
        deque<int> deq; // 双向队列deque
    public:
        MaxQueue() {
        
        
        }
        int max_value() {
        
            return deq.empty() ? -1 : deq.front(); // deque为空，返回-1；否则返回deque首元素
        }
        void push_back(int value) {
        
            que.push(value);  // 元素入队queue
            while (!deq.empty() && deq.back() < value)
                deq.pop_back();  // 将队列deque中队尾所有小于value的元素弹出
            deq.push_back(value);  // 将元素 value 入队 deque
        }
        int pop_front() {
        
            if (que.empty()) 
                return -1; // 若队列queue为空，返回-1
            int val = que.front();  // 获得queue 首元素
            if (val == deq.front())
                deq.pop_front(); // 若 deque 首元素和 queue 首元素 相等 ， deque 首元素出队
            que.pop();
            return val;
        }
    };
    
    
    void test01()
    {
        
        MaxQueue MaxQueue;
        MaxQueue.push_back(5); // 元素5入队queue，同时入队deque
        MaxQueue.push_back(1); // 元素1入队queue，同时入队deque
        cout << MaxQueue.max_value() << endl; // 最大值5
    
        MaxQueue.push_back(3); // 元素3入队queue，deque尾部所有小于3的元素出队，元素3入队deque
        cout << MaxQueue.pop_front() << endl; // 元素5出队queue，元素5出队deque
        cout << MaxQueue.max_value() << endl; // 最大值3
        cout << MaxQueue.pop_front() << endl; // 元素1出队queue，元素1非最大值故不出队deque
    }
    
    int main()
    {
        
        test01();
    
        system("pause");
        return 0;
    }

![在这里插入图片描述][e2f4e2daf94d4dd6adfde8130db11302.png_pic_center]

#### Python版本 ####

import queue
    
    class MaxQueue:
        def __init__(self):
            self.queue = queue.Queue()  # 队列queue
            self.deque = queue.deque()  # 双向队列deque
    
        def max_value(self):
            return self.deque[0] if self.deque else -1 # deque为空，返回-1；否则返回deque首元素
    
        def push_back(self, value):
            self.queue.put(value)   # 元素入队queue
            while self.deque and self.deque[-1] < value: 
                self.deque.pop()    # 将队列deque中队尾所有小于value的元素弹出
            self.deque.append(value) # 将元素 value 入队 deque
    
        def pop_front(self):
            if self.queue.empty(): 
                return -1  # 若队列queue为空，返回-1
            val = self.queue.get() # 获得queue 首元素
            if val == self.deque[0]:
                self.deque.popleft() # 若 deque 首元素和 queue 首元素 相等 ， deque 首元素出队
            return val
    
    def test01():
        maxqueue = MaxQueue()
        maxqueue.push_back(5)  # 元素5入队queue，同时入队deque
        maxqueue.push_back(1)  # 元素1入队queue，同时入队deque
        print(maxqueue.max_value())  # 最大值5
        maxqueue.push_back(3)  # 元素3入队queue，deque尾部所有小于3的元素出队，元素3入队deque
        print(maxqueue.pop_front()) # 元素5出队queue，元素5出队deque
        print(maxqueue.max_value()) # 最大值3
        print(maxqueue.pop_front()) # 元素1出队queue，元素1非最大值故不出队deque
                
    if __name__=="__main__":
        test01()

![在这里插入图片描述][bac70446f1774cf7af4aa1e9ea5ef34e.png_pic_center]

#### Java版本 ####

package com.hailei_01;
    
    import java.util.Deque;
    import java.util.LinkedList;
    import java.util.Queue;
    
    public class maxQueue {
        
        public static void main(String[] args) {
        
    
            MaxQueue maxQueue = new MaxQueue();
            maxQueue.push_back(5);
            maxQueue.push_back(1);
            System.out.println(maxQueue.max_value());
            maxQueue.push_back(3);
            System.out.println(maxQueue.pop_front());
            System.out.println(maxQueue.max_value());
            System.out.println(maxQueue.pop_front());
    
        }
    
        public static class MaxQueue {
        
            Queue<Integer> queue;
            Deque<Integer> deque;
            public MaxQueue() {
        
                queue = new LinkedList<>();
                deque = new LinkedList<>();
            }
            public int max_value() {
        
                return deque.isEmpty() ? -1 : deque.peekFirst();
            }
            public void push_back(int value) {
        
                queue.offer(value);
                while(!deque.isEmpty() && deque.peekLast() < value)
                    deque.pollLast();
                deque.offerLast(value);
            }
            public int pop_front() {
        
                if(queue.isEmpty()) return -1;
                if(queue.peek().equals(deque.peekFirst()))
                    deque.pollFirst();
                return queue.poll();
            }
        }
    }

![在这里插入图片描述][831459da229142a38d550e282f04f72a.png_pic_center]

**希望本文对大家有帮助，上文若有不妥之处，欢迎指正**

**分享决定高度，学习拉开差距**

[e2f4e2daf94d4dd6adfde8130db11302.png_pic_center]: https://img-blog.csdnimg.cn/e2f4e2daf94d4dd6adfde8130db11302.png#pic_center
[bac70446f1774cf7af4aa1e9ea5ef34e.png_pic_center]: https://img-blog.csdnimg.cn/bac70446f1774cf7af4aa1e9ea5ef34e.png#pic_center
[831459da229142a38d550e282f04f72a.png_pic_center]: https://img-blog.csdnimg.cn/831459da229142a38d550e282f04f72a.png#pic_center