剑指offer59-Ⅱ(中等)：队列的最大值

题目

剑指offer59-Ⅱ：队列的最大值

请定义一个队列并实现函数 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]

代码

采用两个队列实现。

class MaxQueue {
	
	//声明一个普通队列
	Queue<Integer> que;
	//声明一个双端单调队列
	Deque<Integer> deq;
   
    //构造方法，类的初始化
    public MaxQueue() {
    	
 	    //实例化队列
    	que= new LinkedList<>();//普通队列，执行正常操作
    	deq= new LinkedList<>();//双端单调队列，辅助普通队列找最大值
    	
    }
    
    //找队列中的最大值
    public int max_value() {
    	
    	if(deq.isEmpty()) {
    		return -1;
    	}
    	
    	return deq.peekFirst();

    }
    
   //入队
    public void push_back(int value) {
    	
    	que.offer(value);
    	
    	while(!deq.isEmpty() && deq.peekLast()<value) {
    		deq.pollLast();
    	}
    	deq.offerLast(value);
    	

    }
    
    //出队
    public int pop_front() {
    	if(que.isEmpty()) {
    		return -1;
    	}
    	
    	if(que.peek().equals(deq.peekFirst())) {
    		deq.pollFirst();
    	}	
    		
    	return que.poll();
    }   
}

随笔

java类Queue

1、创建一个普通队列

Queue<Integer> que = new LinkedList<>();

2、常用方法

（1）isEmpty()

判断队列是否为空。

参数列表：无

返回值类型：boolean

（2）offer(Integer value)

入队。

参数列表：integer value

返回值类型：boolean

（3）poll()

出队并返回值。

参数列表：无

返回值类型：int

（4）peek()

查看队首元素。

参数列表：无

返回值类型：int

java类Deque

1、创建一个双端队列

Deque<Integer> deq = new LinkedList<>();

2、常用方法

（1）isEmpty()

判断队列是否为空。

参数列表：无

返回值类型：boolean

（2）offerFirst(integer value) 和 offerLast(integer value)

从首端入队；从尾端入队

参数列表：int value

返回值类型：boolean

（3）pollFirst() 和 pollLast()

从首端出队并返回值；从尾端出队并返回值

参数列表：无

返回值类型：int

（4）removeFirst()和removeLast()

从首端删除元素并返回值；从尾端删除元素并返回值

参数列表：无

返回值类型：int

​ 与pollFirst() 和 pollLast()的功能没啥区别。

（5）peekFirst() 和 peekLast()

查看首端元素；查看尾端元素

参数列表：无

返回值类型：int

时间复杂度分析

1、max_value()

每次时间复杂度都是O(1)，直接返回双端队列的首端元素。

2、push_back()

均摊时间复杂度为O(1)（并不一定每次时间复杂度都是O(1)），例如 76543218 ，最后一次 push_back 操作是O(n)，其他每次push_back 操作都是O(1)，均摊时间复杂度为(O(1)×(n-1)+O(n))/n=O(1)。

3、pop_front()

每次时间复杂度都是O(1)，从普通队列里出一个元素，如果该元素恰好是最大值，双端队列的首端元素也出队，仍然是常数时间复杂度。

小结：

在时间复杂度为O(1)的情况下，找栈或队列的最大值或最小值，往往需要一个辅助的数据结构来实现，具体选用什么样的数据结构需要在做题过程中进行总结。