哈尔滨专业网站建设定制,西安做网站哪家比较好,吴川市建设工程公司网站,html解析wordpress简介
队列也是一种受限制的线性表和栈相类似#xff0c;栈是先进后出#xff0c;而队列是先进先出#xff0c;就好像一没有底的桶#xff0c;往里面放东西#xff0c;如图 在这里也是用数组来实现队列#xff0c;用数组实现的叫做顺序队列
队列的数组模拟
const int N…简介
队列也是一种受限制的线性表和栈相类似栈是先进后出而队列是先进先出就好像一没有底的桶往里面放东西如图 在这里也是用数组来实现队列用数组实现的叫做顺序队列
队列的数组模拟
const int N 1000010;//在队尾插入元素 队头弹出元素
int q[N],hh,tt-1; //hh代表队头 tt代表队尾//插入
q[tt] x ;//弹出
hh ;//判断队列是否为空
if(hh tt ) not empty
else empty//取出队头元素
q[hh] ;
单调队列
单调队列也就是说其中的元素始终保持单调性
常见应用找出滑动窗口中的最大值/最小值 如题给定一个大小为 n ≤ 10^6 的数组。 有一个大小为 k 的滑动窗口它从数组的最左边移动到最右边。 你只能在窗口中看到 k 个数字。 每次滑动窗口向右移动一个位置。 以下是一个例子 该数组为 [1 3 -1 -3 5 3 6 7]k 为 3。 输入格式 输入包含两行。 第一行包含两个整数 n 和 k分别代表数组长度和滑动窗口的长度。 第二行有 n 个整数代表数组的具体数值。 同行数据之间用空格隔开。 输出格式 输出包含两个。 第一行输出从左至右每个位置滑动窗口中的最小值。 第二行输出从左至右每个位置滑动窗口中的最大值。 输入样例 8 3
1 3 -1 -3 5 3 6 7 输出样例 -1 -3 -3 -3 3 3
3 3 5 5 6 7 例子的输出解释 窗口的位置 最小值 最大值【1 3 -1】 -3 5 3 6 7 -1 31【 3 -1 -3】 5 3 6 7 -3 31 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
对于解开这题我们依旧尝试暴力做法
既然求滑动窗口中的最大值和最小值那我们只需要让窗口滑动 n - k 1 次再每次都对窗口里的k个数求出最大/小值就可以了以下是部分代码
//求最小值
for (int i 0 ; i n - k 1 ; i)
{int min -1;for (int j i; j i k; j){if (a[i] min){min a[i];}}printf(%d , min);
}
//求最大值
// 这样的做法不仅要遍历数组一遍在这个过程中窗口还要遍历相当于遍历了 n * k 遍非常浪费时间。
优化的方向也是和之前的单调栈类似有很多元素根本就不可以在后边用到 例如 我们求最小值时当 a [ x ] a [ y ] 并且 x y 这种情况就可以将 a [ x ] 从我们这个队列删除 反之易得。 这就得到了队列的单调性 对于这个循环中我们需要做3个步骤
1. 检测队列是否为空 并且 队头是否滑出了窗口这是什么意思呢窗口的大小固定是 k 我们要保证队列中的元素全是窗口里的数的下标队头保存的下标如果是窗口左边的下标就说明要将队头的元素移出队列这里只需要判断一次因为每次循环最多添加一个元素
2. 检测队列是否为空 并且队尾所指向的元素是否大于等于此时的元素如果为真要将队尾移出队列
3.再将我们此时指向的元素的下标加入队列
4.打印最小值肯定不是每一次循环都需要打印你会发现前 k - 1 次不需要打印,变成 i 的话就是i k - 1i从0开始因为此时窗口都没有满
现在将以上步骤变成代码
#define _CRT_SECURE_NO_WARNINGS 1#include iostreamusing namespace std;const int N 1000010;
int n, k;
int a[N], q[N]; //q 数组是队列
int hh, tt -1; //hh是队头 tt是队尾int main(void)
{scanf(%d%d, n, k);for (int i 0; i n; i){scanf(%d, a[i]);}for (int i 0; i n; i){if (hh tt q[hh] i - k 1) hh; // i - k 1 就是窗口的最左边的下标while (hh tt a[q[tt]] a[i]) tt--;q[tt] i;if (i k - 1 ) printf(%d , a[q[hh]]);}puts(); //打印空字符串,虽然打印为空但是使用 puts() 显示字符串时系统会自动在其后添加一个换行符hh 0, tt -1; //记得要初始化数列for (int i 0; i n; i){if (hh tt q[hh] i - k 1) hh; while (hh tt a[q[tt]] a[i]) tt--;q[tt] i;if (i k - 1) printf(%d , a[q[hh]]);}puts(); return 0;
}
运行图 成功得到结果
