题目描述
有一个 1 ∗ n 的矩阵，有 n 个正整数。
现在给你一个可以盖住连续的 k 的数的木板。
一开始木板盖住了矩阵的第 1 ∼ k 个数，每次将木板向右移动一个单位，直到右端与第 n 个数重合。
每次移动前输出被覆盖住的最大的数是多少。
输入输出格式
输入格式：
第一行两个数，n，k，表示共有 n 个数，木板可以盖住 k 个数。
第二行 n 个数，表示矩阵中的元素。
输出格式：
共 n − k + 1 行，每行一个正整数。
第 i 行表示第 i ∼ i + k − 1 个数中最大值是多少。
输入输出样例
说明
对于 20% 的数据保证：1 ≤ n ≤ 1e3，1 ≤ k ≤ n
对于 50% 的数据保证：1 ≤ n ≤ 1e4，1 ≤ k ≤ n
对于 100% 的数据保证：1 ≤ n ≤ 2 ∗ 1e6，1 ≤ k ≤ n
矩阵中元素大小不超过 1e4。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=2e6+10; 4 int a[N],n,k,tot,q[N],head; 5 int main() { 6 scanf("%d%d", &n, &k); 7 for (int i = 1; i <= n; i++) { 8 scanf("%d", &a[i]); 9 } 10 head = tot = 1; 11 q[1] = 1; 12 for (int i = 1; i <= n; i++) { 13 if (q[head] <= i - k) { 14 head++; 15 } 16 while (tot >= head && a[q[tot]] <= a[i]) { 17 tot--; 18 } 19 q[++tot] = i; 20 if (i >= k) { 21 printf("%d ", a[q[head]]); 22 } 23 } 24 }
思路：
实际上就是单调队列的直接应用。以维护每个滑动窗口的最大值为例
• 维护一个下标和元素值都单调递增的队列
• 每次滑动窗口往后移动新增一个元素，当前队列队尾比它还大的元素显然是没用的，可以直接删掉。这样队列中保存的都是“有用”
的东西
• 当队头的元素超出了窗口的范围，就要删掉
• 这么一番操作后，数据结构的性质没有发生变化
• 答案就是队头元素的值