四大门户网站是哪些,电竞网站开发需求报告,哪家做网站的公司比较好,重庆做网站熊掌号Description
有一个长为 n 的序列 a#xff0c;以及一个大小为 k 的窗口。现在这个从左边开始向右滑动#xff0c;每次滑动一个单位#xff0c;求出每次滑动后窗口中的最大值和最小值。
例如#xff1a;
The array is [1,3,−1,−3,5,3,6,7] and k3。 Input
输入一共有…Description
有一个长为 n 的序列 a以及一个大小为 k 的窗口。现在这个从左边开始向右滑动每次滑动一个单位求出每次滑动后窗口中的最大值和最小值。
例如
The array is [1,3,−1,−3,5,3,6,7] and k3。 Input
输入一共有两行第一行有两个正整数 n,k。 第二行 n 个整数表示序列 a
Output
输出共两行第一行为每次窗口滑动的最小值 第二行为每次窗口滑动的最大值
Sample 1
InputcopyOutputcopy 8 3
1 3 -1 -3 5 3 6 7 -1 -3 -3 -3 3 3
3 3 5 5 6 7
Hint
【数据范围】 对于50% 的数据1≤n≤10^5 对于100% 的数据1≤k≤n≤10^6ai∈[−231,231)。 #includeiostream
using namespace std;
const int N 1e6 10;
int a[N], maxq[N], minq[N];
int n, m;//h是队头用于输出答案t是队尾用于加入和删除元素
//注意对头为左队尾为右队头只出队尾可出可进因此若队内有元素则ht
//max队内的元素因保持单调递减的性质加入的不是元素值而是元素所在数组a中的下标
void maxfind() {int h 0, t -1;for (int i 1; i n; i){if (h t maxq[h] i - m) h; //不在当前滑动窗口的元素删除while (h t a[i] a[maxq[t]]) t--; //a[i]为当前元素若当前元素大于队尾的元素则需要删除时其满足单调递减的性质maxq[t] i; //加入新元素的下标if(im) cout a[maxq[h]] ;//输出结果}
}
//原理同上
void minfind() {int h 0, t -1;for (int i 1; i n; i){if (h t minq[h] i - m) h;while (h t a[i] a[minq[t]]) t--;minq[t] i;if(im) cout a[minq[h]] ;}
}int main()
{cin n m;for (int i 1; i n; i) cin a[i];minfind();cout endl;maxfind();return 0;
} 单调队列模板滑动窗口_滑动窗口 /【模板】单调队列_胡牧之.的博客-CSDN博客
