GabWiki

Appearance

单调队列 ​

模板题：找出滑动窗口中的最大值/最小值

C++
int que[N], hh = 0, tt = -1;
for (int i = 0; i < n; ++i) {
    while (hh <= tt && check_out(que[hh])) ++hh; // 判断队头是否滑出窗口
    while (hh <= tt && check(que[tt], nums[i])) --tt;
    q[++tt] = i;
}
int que[N], hh = 0, tt = -1;
for (int i = 0; i < n; ++i) {
    while (hh <= tt && check_out(que[hh])) ++hh; // 判断队头是否滑出窗口
    while (hh <= tt && check(que[tt], nums[i])) --tt;
    q[++tt] = i;
}

应用 ​

求滑动窗口最小值 ​

C++
// 数字序列长度为n  序列输入至a[0...n] 滑动窗口长度为k
int que[N], hh = 0, tt = -1; // 数组模拟双端队列

for (int i = 0; i < n; ++i) {
    if (hh <= tt && i - que[hh] == k) ++hh;
    while (hh <= tt && a[que[tt]] >= a[i]) --tt;
    que[++tt] = i;
    if (i >= k - 1) printf("%d ", a[que[hh]]); // 输出滑动窗口最小值(仅在滑动窗口中元素满k个时输出)
}
// 数字序列长度为n  序列输入至a[0...n] 滑动窗口长度为k
int que[N], hh = 0, tt = -1; // 数组模拟双端队列

for (int i = 0; i < n; ++i) {
    if (hh <= tt && i - que[hh] == k) ++hh;
    while (hh <= tt && a[que[tt]] >= a[i]) --tt;
    que[++tt] = i;
    if (i >= k - 1) printf("%d ", a[que[hh]]); // 输出滑动窗口最小值(仅在滑动窗口中元素满k个时输出)
}

求滑动窗口最大值 ​

C++
// 数字序列长度为n  序列输入至a[0...n] 滑动窗口长度为k
int que[N], hh = 0, tt = -1; // 数组模拟双端队列

for (int i = 0; i < n; ++i) {
    if (hh <= tt && i - que[hh] == k) ++hh;
    while (hh <= tt && a[que[tt]] <= a[i]) --tt;
    que[++tt] = i;
    if (i >= k - 1) printf("%d ", a[que[hh]]); // 输出滑动窗口最大值(仅在滑动窗口中元素满k个时输出)
}
// 数字序列长度为n  序列输入至a[0...n] 滑动窗口长度为k
int que[N], hh = 0, tt = -1; // 数组模拟双端队列

for (int i = 0; i < n; ++i) {
    if (hh <= tt && i - que[hh] == k) ++hh;
    while (hh <= tt && a[que[tt]] <= a[i]) --tt;
    que[++tt] = i;
    if (i >= k - 1) printf("%d ", a[que[hh]]); // 输出滑动窗口最大值(仅在滑动窗口中元素满k个时输出)
}