avatar

单调队列

单调队列

场景: 滑动窗口,经典问题

模板

常见模型:找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
while (hh <= tt && check_out(q[hh])) hh ++ ; // 判断队头是否滑出窗口
while (hh <= tt && check(q[tt], i)) tt -- ;
q[ ++ tt] = i;
}

题目

AcWing

  • 154 滑动窗口

Ac154 滑动窗口

描述

给定一个大小为n≤106的数组。

有一个大小为k的滑动窗口,它从数组的最左边移动到最右边。

您只能在窗口中看到k个数字。

每次滑动窗口向右移动一个位置。

以下是一个例子:

该数组为[1 3 -1 -3 5 3 6 7],k为3。

窗口位置 最小值 最大值
[1 3 -1] -3 5 3 6 7 -1 3
1 [3 -1 -3] 5 3 6 7 -3 3
1 3 [-1 -3 5] 3 6 7 -3 5
1 3 -1 [-3 5 3] 6 7 -3 5
1 3 -1 -3 [5 3 6] 7 3 6
1 3 -1 -3 5 [3 6 7] 3 7

思路:

  • 普通队列的做法
  • 将队列中没有用的元素删除 —单调性
  • 可以从对头或者队尾取出最值
解答

可以分成两部分,最小值和最大值

import java.io.*;
import java.util.*;

public class Main {
static final int N = 1000010;
static int[] q = new int[N]; //队列
static int[] arr = new int[N];
static int hh = 0, tt = -1; //对头和队尾
public static void main(String[] args) throws IOException{
BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

String[] s1 = br.readLine().split(" ");
int n = Integer.parseInt(s1[0]); //数组长度
int k = Integer.parseInt(s1[1]); //窗口长度
//数组
String[] s = br.readLine().split(" ");
for(int i=0;i<n;i++) {
arr[i]=Integer.parseInt(s[i]);
}


//q队列中存的是下标哦,很重要


//1. 最小值
for(int i=0;i<n;i++){
//hh <= tt 就是队列不为空
//判断队头是否已经滑出窗口, 如果滑出窗口, 则弹出队首元素,
// 维护窗口大小不超过 k, 每次值滑动一次, 所以可以使用 if
if(hh<=tt && i-k+1>q[hh]){
hh++;
}
//寻找窗口中的最小值
while(hh<=tt&&arr[q[tt]]>=arr[i]){
tt--;
}

q[++tt] = i; // 将本轮下标添加到队列中
//保证窗口的大小,比如窗口大小为 3, 不能此时只进入 2个数字
if (i + 1 >= k) log.write(arr[q[hh]] + " "); // 窗口内的最小值为队首元素
}

log.write("\n");
hh = 0;
tt = -1;
// 查找最大值

//2. 最大值
for(int i=0;i<n;i++){
if(hh<=tt && i-k+1>q[hh]){
hh++;
}
//最大值
while(hh<=tt&&arr[q[tt]]<arr[i]){
tt--;
}
q[++tt]=i;
if (i + 1 >= k) log.write(arr[q[hh]] + " ");
}

// 关闭输入输出流
log.flush();
reader.close();
log.close();


}
}

多思考

找最小值,保证是上升的,最大值,保证下降的

Others

人无完人,何况是小白Chen我呢,文章难免会出现一些错误,若是读者们发现错误,可以评论或者联系我,Chen会尽力改正,给大家更优秀的博文。

文章作者: Chen
文章链接: https://vccyb.gitee.io/myblog/2020/03/24/Algorithm/articleM-16/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 东川
打赏
  • 微信
    微信
  • 支付寶
    支付寶

评论