单调队列

“如果一个选手比你小还比你强，你就可以退役了。”——单调队列的原理

单调队列主要的解决问题：单调队列是一种主要用于解决滑动窗口类问题的数据结构，即，在长度为 n 的序列中，求每个长度为 m 的区间的区间最值。它的时间复杂度是 O(n);

由于是维护区间所以需要两边都需要能够吐出数字，所以需要用双向队列进行维护

例题

给定一个长度为n的数组a。

有一个大小为k的滑动窗口（窗口中只能看到k个元素），它从数组的最左边，每次向右移动一个位置，直到移动到最右边。

你需要回答出滑动窗口在每个位置时，窗口中的最大值和最小值。

输入

第一行：两个整数n,k。（51≤k≤n≤2×10^5）

第二行：n个整数，代表数组a。（−10^6≤ai​≤10^6，1≤i≤n）

输出

第一行：从左到右，滑动窗口在每个位置的最大值。

第二行：从左到右，滑动窗口在每个位置的最小值。

样例输出

8 3
0 3 1 0 -5 2 1 8

样例输出

3 3 1 2 2 8
0 0 -5 -5 -5 1

ANSWER

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

constexpr int N = 2e5 + 10;

int a[N];

void solve() {

  int n, k;//k代表的是队列的长度

  cin >> n >> k;

  for (int i = 1; i <= n; i++) cin >> a[i];

  deque<int> dq;//存的是坐标

  for (int i = 1; i <= n; i++) {
//这里求的是最大值,单调队列要求单调性。
  while (dq.size() && dq.front() <= i - k) dq.pop_front();
//-|-|-|-|------相当于最前面是前端，最后面是后端,就是现在的i超过了，那么将前面的吐出来。
  while (dq.size() && a[dq.back()] <= a[i]) dq.pop_back();
//就是会前进一格的时候就要判断如果前面的比现在的要大，由于求的是最大值，所以要求的从大到小所以大的小的就可以被删掉，因为它已经不会成为答案。
  dq.push_back(i);
// 将i读入进去
  if (i >= k) cout << a[dq.front()] << ' ';
}

  cout << '\n';

  dq = deque<int>();

  for (int i = 1; i <= n; i++) {

    while (dq.size() && dq.front() <= i - k) dq.pop_front();

    while (dq.size() && a[dq.back()] >= a[i]) dq.pop_back();

    dq.push_back(i);

    if (i >= k) cout << a[dq.front()] << ' ';

  }

 cout << '\n';

}

int main() {

  ios::sync_with_stdio(0);

  cin.tie(0);

  cout.tie(0);

  int t = 1;

  while (t--) {

   solve();

  }

}

数组实现

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

constexpr int N = 2e5 + 10;

int a[N],dq[N];

void solve() {

int n, k;

cin >> n >> k;

int hh =1,tt = 0 ;

for (int i = 1; i <= n; i++) cin >> a[i];

for (int i = 1; i <= n; i++) {

while (hh<=tt && dq[hh] <= i - k) hh++;

while (hh<=tt && a[dq[tt]]<= a[i]) tt--;

dq[++ tt] = i;

if (i >= k) cout << a[dq[hh]] << ' ';

}

cout << '\n';

hh =1,tt = 0;

for (int i = 1; i <= n; i++) {

while (hh<=tt && dq[hh]<=i-k) hh++;

while (hh<=tt && a[dq[tt]] >= a[i]) tt--;

dq[++ tt] = i;

if (i >= k) cout << a[dq[hh]] << ' ';

}

cout << '\n';

}

int main() {

ios::sync_with_stdio(0);

cin.tie(0);

cout.tie(0);

int t = 1;

while (t--) {

solve();

}

}