题目链接：https://www.acwing.com/problem/content/75/
参考链接：https://www.cnblogs.com/baccano-acmer/p/9997514.html
单调队列，即单调递减或单调递增的队列。使用频率不高，但在有些程序中会有非同寻常的作用
单调队列的舞台
由于单调队列的队头每次一定最小值，故查询为O(1)。
进队出队稍微复杂点：
进队时，将进队的元素为e，从队尾往前扫描，直到找到一个不大于e的元素d，将e放在d之后，舍弃e之后的所有元素；如果没有找到这样一个d，则将e放在队头(此时队列里只有这一个元素)。保证队列是单调增加的。
出队时，对于单调队列，只需判断队头是否已经超出滑动窗口范围，若超出，则从队头退队。。
分析单调队列的时间复杂度，每个元素最多入队1次、出队1次，且出入队都是O(1)的，因此这是一个总时间O(n)的算法。
Java版本算法模板：
import java.util.LinkedList;
import java.util.Scanner;
public class Main1 {
static class node{
int num;
int id;
public int getNum() {
return num;
}
public void setNum(int num) {
this.num = num;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public node(int num, int id) {
this.num = num;
this.id = id;
}
public node() {
}
}
public static void main(String[] args) {
LinkedList<node> q1=new LinkedList<node>();
LinkedList<node> q2=new LinkedList<node>();
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int k=sc.nextInt();
int a[]=new int[n+2];
for (int i = 1; i <=n; i++) {
a[i]=sc.nextInt();
}
for(int i=1;i<=n+1;i++)
{
if(!q1.isEmpty())
{
if(q1.peek().id+k<i)
q1.removeLast();
if(i>=1+k)
System.out.print(q1.peek().num+" ");
}
while(!q1.isEmpty()&&q1.peekLast().num>=a[i]&&i<=n)
q1.removeLast();
q1.add(new node(a[i],i));
}
System.out.println();
for(int i=1;i<=n+1;i++)
{
if(!q2.isEmpty())
{
if(q2.peek().id+k<i)//队列首的元素是否已经过期
q2.removeFirst();
if(i>=1+k)//至少滑动k个单位才需要输出
System.out.print(q2.peek().num+" ");
}
while(!q2.isEmpty()&&q2.peekLast().num<=a[i]&&i<=n)
q2.removeLast();
q2.add(new node(a[i],i));
}
}
}
以上的算法模板分别是求滑动窗口的最小值和最大值。
对于oj上的题目的算法应用是：
class Solution {
static class node{
int num;
int id;
public int getNum() {
return num;
}
public void setNum(int num) {
this.num = num;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public node(int num, int id) {
this.num = num;
this.id = id;
}
public node() {
}
}
public int[] maxInWindows(int[] nums, int k) {
ArrayList<Integer> res=new ArrayList<Integer>();
LinkedList<node> q2=new LinkedList<node>();
int n=nums.length;
int a[]=new int[n+2];
for (int i = 1; i <=n; i++) {
a[i]=nums[i-1];
}
for(int i=1;i<=n+1;i++)
{
if(!q2.isEmpty())
{
if(q2.peek().id+k<i)//队列首的元素是否已经过期
q2.removeFirst();
if(i>=1+k)//至少滑动k个单位才需要输出
//System.out.print(q2.peek().num+" ");
res.add(q2.peek().num);
}
while(!q2.isEmpty()&&q2.peekLast().num<=a[i]&&i<=n)
q2.removeLast();
q2.add(new node(a[i],i));
}
int arr[]=new int[res.size()];
for (int i = 0; i < arr.length; i++) {
arr[i]=res.get(i);
}
return arr;
}
}
单调队列一般是使用在动态规划中。