算法笔记：单调队列
单调队列：
队列元素之间的关系具有单调性（从队首到队尾单调递增/递减），队首和队尾都可以进行入队出队（即插入删除）操作，本质是由双端队列deque实现。
适用问题
通常解决动态小区间中寻找极值问题。
思路：
由于需要比较在一个窗口里面的最大值的问题，最暴力的解法就是每次都去遍历窗口中的元素，然后取极大值，但这种情况只要K稍微大一点性能便会很差，而单调队列可以只进行维护最大值的操作，来优化性能。在本题中，关键的就是一个窗口中最大值在下一次移动的留存问题需要注意，比如[4,2,1],k=2,时，首先窗口为[4,2]那么此时单调队列中的元素就为[2.4]，4在队首的位置，那么下一次移动窗口成为[2,1]由于4是上一个窗口的最大值，但也是边界元素，下一次移动就会需要剔除，而单调队列恰好可以做到，那么此时4会从队首弹出，那么队列中次大的2就到队首，那么就和新进来的元素1比对来取值。
单调队列是通过双端队列Deque对象来进行操作，即可以进行头尾操作。
流程是当一个队列入队时，从尾部不断弹出元素进行比较，如果元素比队列中的元素大，那么就将队列中的元素弹出，直到存放到不大于队列中的元素的后面，或者最前面。
一个很有意思的描述。
代码：
class Solution {
public static Deque<Integer> queue=new LinkedList<>();
public int[] maxSlidingWindow(int[] nums, int k) {
//思路：单调队列
//java中的API Deque:双端队列 可以同时进行头尾操作
//从队头进行出元素 队尾进元素
Queue<Integer> result=new LinkedList<>(); //存放结果队列
if(k==1){
int [] ex=new int[nums.length];
for(int c=0;c<nums.length;c++){
ex[c]=nums[c];
}
return ex;
}
//先初始化 第一个窗口
for(int x=0;x<k;x++){
push(nums[x]); //调用入栈操作
}
result.offer(queue.peekFirst());
pop(nums[0]); //判断左指针是否是最大值下标 不是则不用管
//开始从第一个窗口后进行判断
for(int left=1,right=k;right<nums.length;){
//那么第二个窗口和第一个窗口的区别就是要 判断左指针的元素是否是当前窗口最大值 右指针的元素是否比当前窗口最大值大
//先判断当前右指针 使右指针元素入队
push(nums[right]);
//右指针入队后 查看队首的最大值
result.offer(queue.peekFirst()); //将最大值存入结果队列
//然后需要在移动指针前判断当前左指针是否是最大元素
pop(nums[left]); //如果是就需要弹出队首元素
left++;
right++;
}
Object [] r=new Object[result.size()];
r=result.toArray();
int [] R=new int[r.length];
for(int y=0;y<R.length;y++){
R[y]=Integer.parseInt(String.valueOf(r[y]));
}
queue.clear();
return R;
}
public static void push(int x){ // 入队方法 需要从队尾去判断元素大小
while(!queue.isEmpty()&&queue.peekLast()<x){ //队列首先不能为空 然后从队尾拿元素 如果目标值大于队尾元素 则将队尾元素弹出
queue.pollLast(); //将所有小于目标值的队尾元素弹出
}//所有元素已经弹出
//然后将该元素放置队尾
queue.offerLast(x);
//这样做是因为 只需要维护一个滑动窗口中的最大值即可，其余元素不用维护 当滑动窗口变动时 只需要关注最大值的那个元素是否被移除
}
public static void pop(int y){
//出队方法是当滑动窗口左指针移动时 需要判断移出去的那个左边的元素是否是最大值,如果是最大值就需要调用该方法 将单调队列中的最大值弹出
if(!queue.isEmpty()&&y==queue.peekFirst()){
queue.pollFirst();//弹出队首元素
}
} //出队方法 从队头出队拿元素
}原文地址：https://blog.csdn.net/Tomkruse11/article/details/144028362
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！