考点：本题考查队列和知识迁移能力
题目一描述：滑动窗口的最大值
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。
例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，{[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}，他们的最大值分别为{4,4,6,6,6,5}
思路：双端队列
建立一个两端开口的队列，用来保存有可能是滑动窗口最大值的数字的下标。在存入一个数字的下标之前，首先要判断队列里已有数字是否小于待存入的数字。如果已有的数字小于待存入的数字，那么这些数字已经不可能是滑动窗口的最大值，因此它们将会被依次从队列的尾部删除（调用函数.removeLast()）。同时，如果队列头部的数字已经从窗口里滑出（队列头部的数字如果其下标离滑动窗口末尾的距离大于窗口大小），那么滑出的数字也需要从队列的头部删除（调用函数.removeFirst()）。由于队列的头部和尾部都有可能删除数字，这是需要两端开口的队列的原因。
import java.util.ArrayList;
import java.util.ArrayDeque;//ArrayDeque类提供了可调整大小的阵列
public class Solution {
public ArrayList<Integer> maxInWindows(int [] num, int size)
{
ArrayList<Integer> result = new ArrayList<>();
if(num == null||num.length <= 0||size <= 0||size > num.length)
return result;
//队列中存放的是数组下标
ArrayDeque<Integer> indexDeque = new ArrayDeque<Integer>();
for(int i=0;i<size-1;i++){
while(!indexDeque.isEmpty() && num[i]> num[indexDeque.getLast()])
indexDeque.removeLast();
indexDeque.addLast(i);
}
for(int i=size-1;i<num.length;i++){
while(!indexDeque.isEmpty() && num[i]> num[indexDeque.getLast()])
indexDeque.removeLast();
if(!indexDeque.isEmpty() && (indexDeque.getFirst()<=(i-size)))
indexDeque.removeFirst();
indexDeque.addLast(i);
result.add(num[indexDeque.getFirst()]);
}
return result;
}
}
ArrayDeque双端队列常用的方法
题目二描述：队列的最大值
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
输入:
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]
思路：双端队列同上
class MaxQueue {
private ArrayDeque<Integer> valueDeque = new ArrayDeque<Integer>() ;
private ArrayDeque<Integer> maxValueDeque = new ArrayDeque<Integer>() ;
public MaxQueue() {
}
public int max_value() {
if(!maxValueDeque.isEmpty())
return maxValueDeque.peek();
return -1;
}
public void push_back(int value) {
valueDeque.addLast(value) ;
while (!maxValueDeque.isEmpty() && maxValueDeque.getLast() < value) {
maxValueDeque.pollLast() ;
}
maxValueDeque.addLast(value) ;
}
public int pop_front() {
if (valueDeque.isEmpty())
return -1 ;
else{
int result = valueDeque.pollFirst() ;
if (result == maxValueDeque.peek())
maxValueDeque.pollFirst() ;
return result ;
}
}
}
/**
* Your MaxQueue object will be instantiated and called as such:
* MaxQueue obj = new MaxQueue();
* int param_1 = obj.max_value();
* obj.push_back(value);
* int param_3 = obj.pop_front();
*/
