一道非常经典的队列题
共 2313字,需浏览 5分钟
· 2020-11-11
队列的最大值
题目来源:剑指offer59
今天发一道剑指offer上面的经典题目,主要考察面试者的知识迁移能力,下面我们先来看一下题目描述。
请定义一个队列并实现函数 max_value 得到队列里的最大值,若队列为空,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]
输入的第一行代表的执行函数,第二行代表的是输入的值,该题中只有我们的push_back传入了参数,输出代表的为执行该函数时,函数的返回值。
个人认为这个题目还是很不错的,而且也有一定的难度,大家可以试着实现一下。
为保证严谨性,文章中的所有代码都经过测试,大家可以放心食用
暴力解法
暴力法,是因为我们的max值通过每次遍历我们的动态数组来获得。思路很简单,我们创建一个动态数组,我们每次执行max_value函数时,通过遍历数组获得最大值,入队操作则用add,出队操作则用remove(0),去除动态数组的头元素。
题目代码:
class MaxQueue {
//动态数组
ArrayList arr = new ArrayList<>();
public MaxQueue() {
}
public int max_value() {
//为空的情况
if(arr.size() == 0){
return -1;
}
//初始化max
int max = Integer.MIN_VALUE;
//遍历动态数组,获取最大值
for(int i = 0;i
if(arr.get(i)>max){
max = arr.get(i);
}
}
return max;
}
public void push_back(int value) {
//添加元素
arr.add(value);
}
public int pop_front() {
//队列为空时,执行该函数返回-1
if(arr.size() == 0){
return -1;
}else{
return arr.remove(0);
}
}
}
利用双端队列
deque (double-ended queue,双端队列)是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行。
我们了解了双端队列之后,是不是感觉很实用,很灵活,但实际上在应用程序中远不及栈和队列有用。我们了解双端队列之后,我们来聊一下我们的做题思路吧
这个思路也很简单,我们充分利用双端队列的性质,因为它可以两头出队,那我们在双端队列中仅保存队列中每一段的最大值即可,见下图。
我们分成了三段,第一段的最大值为9,第二段为8,第三段为7。那么我们这个段是怎么分的呢?
我们看第一段最大值为9前面没有其他数字,第二段最大值为8,前面的三个数字都小于8,但是它小于第一段的最大值,同理第三段也是。如果第三段的元素为6,10的话,那我们的双端队列中只有10啦,因为它大于它之前的所有值。
废话不多说下面我们直接看动图吧。
题目代码:
class MaxQueue {
Queue queue ;
Deque deque;
public MaxQueue() {
queue = new LinkedList();
deque = new LinkedList();
}
//返回最大值,此时返回的为depue的第一个元素
public int max_value() {
if(deque.isEmpty()){
return -1;
}
int max = deque.getFirst();
return max;
}
//入队操作
public void push_back(int value) {
//普通队列直接入队
queue.offer(value);
//双端队列需要先将该阶段小于value值的出队
while( !deque.isEmpty() && deque.getLast() < value){
deque.removeLast();
}
//入队value
deque.offer(value);
}
//出队操作,返回两种情况,队头小于当前阶段最大值,队头等于当前阶段最大值
public int pop_front() {
if(queue.isEmpty()){
return -1;
}
//普通队列出队
int temp = queue.poll();
//判断普通队列和双端队列的队头是否相等,两种返回情况
if(temp == deque.peekFirst()){
return deque.pollFirst();
}
else{
return temp;
}
}
}
个人感觉今天的题目很nice,考察范围很广,而且这也是一个面试常考题目
![](https://filescdn.proginn.com/bb60a24d83506d6d23fcac387f0f7f40/f47568c42ca385d171c628ae4c8b66e6.webp)
老哥点个在看?