单调队列
场景: 滑动窗口,经典问题
模板
常见模型:找出滑动窗口中的最大值/最小值 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
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]); } 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.write("\n"); hh = 0; tt = -1; 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会尽力改正,给大家更优秀的博文。