做网站接广告,做企业网站找谁,常用的搜索引擎的网站,全屋定制销售技巧题目#xff1a;
154. 滑动窗口 - AcWing题库 代码#xff08;删除队列窗口多余的单调队列#xff09;
判断最值是否滑出窗口可以放在 入队的后面。
但是#xff0c;判断#xff0c;准备入队元素比前面小#xff0c;要从队尾出队#xff0c;放在入队前。
总之
154. 滑动窗口 - AcWing题库 代码删除队列窗口多余的单调队列
判断最值是否滑出窗口可以放在 入队的后面。
但是判断准备入队元素比前面小要从队尾出队放在入队前。
总之是否滑出窗口在最值输出前操作完就行。
单调队列是用来维护当前窗口的主要是多余的删去了
多余值队尾出队因为要将当前最小的输出出去前面更大的都要队尾出去入队将滑出窗口的索引队头出队输出队头索引的值
从最小值输出开始做
队列维护窗口的最小值的索引。每次滑动窗口输出队头索引的数组a值。
#includebits/stdc.h
using namespace std;const int N 1e610;
int n, k;
int q[N], a[N];int main() {cin n k;for(int i 0; i n; i ) cin a[i];int hh 0, tt -1;for(int i 0; i n; i ) {if(hhtt q[hh]i-k1) hh ; // 滑出去了while(hhtt a[q[tt]]a[i]) tt--; //前面的大于后面的去掉前面的q[tt] i; //索引入队if(ik-1) cout a[q[hh]] ; // 从遍历完第一个窗口开始输出栈顶}puts();hh 0, tt -1;for(int i 0; i n; i ) {if(hhtt q[hh]i-k1) hh ;while(hhtt a[q[tt]]a[i]) tt --;q[tt] i;if(ik-1) cout a[q[hh]] ;}puts();return 0;
} 代码使用deque双端队列存窗口最值
#includebits/stdc.h
using namespace std;const int N 1e610;
int a[N];
int main() {int n, k;cin n k;for(int i 0; i n; i ) cin a[i];dequeint q;for(int i 0; i n; i ) {while(q.size() q.back() a[i]) q.pop_back();q.push_back(a[i]);//窗口滑动最小值出去了if(ik q.front() a[i-k]) q.pop_front();if(ik-1) cout q.front() ;}puts();q.clear();for(int i 0; i n; i ) {while(q.size() q.back() a[i]) q.pop_back();q.push_back(a[i]);if(ik-1 q.front() a[i-k]) q.pop_front();if(ik-1) cout q.front() ;}puts();return 0;
}
