跳转至

單調隊列

引入

在學習單調隊列前，讓我們先來看一道例題。

例題

Sliding Window

本題大意是給出一個長度為 \(n\) 的數組，編程輸出每 \(k\) 個連續的數中的最大值和最小值。

最暴力的想法很簡單，對於每一段 \(i \sim i+k-1\) 的序列，逐個比較來找出最大值（和最小值），時間複雜度約為 \(O(n \times k)\)。

很顯然，這其中進行了大量重複工作，除了開頭 \(k-1\) 個和結尾 \(k-1\) 個數之外，每個數都進行了 \(k\) 次比較，而題中 \(100\%\) 的數據為 \(n \le 1000000\)，當 \(k\) 稍大的情況下，顯然會 TLE。

這時所用到的就是單調隊列了。

定義

顧名思義，單調隊列的重點分為「單調」和「隊列」。

「單調」指的是元素的「規律」——遞增（或遞減）。

「隊列」指的是元素只能從隊頭和隊尾進行操作。

Ps. 單調隊列中的 "隊列" 與正常的隊列有一定的區別，稍後會提到

例題分析

解釋

有了上面「單調隊列」的概念，很容易想到用單調隊列進行優化。

要求的是每連續的 \(k\) 個數中的最大（最小）值，很明顯，當一個數進入所要 "尋找" 最大值的範圍中時，若這個數比其前面（先進隊）的數要大，顯然，前面的數會比這個數先出隊且不再可能是最大值。

也就是説——當滿足以上條件時，可將前面的數 "彈出"，再將該數真正 push 進隊尾。

這就相當於維護了一個遞減的隊列，符合單調隊列的定義，減少了重複的比較次數，不僅如此，由於維護出的隊伍是查詢範圍內的且是遞減的，隊頭必定是該查詢區域內的最大值，因此輸出時只需輸出隊頭即可。

顯而易見的是，在這樣的算法中，每個數只要進隊與出隊各一次，因此時間複雜度被降到了 \(O(N)\)。

而由於查詢區間長度是固定的，超出查詢空間的值再大也不能輸出，因此還需要 site 數組記錄第 \(i\) 個隊中的數在原數組中的位置，以彈出越界的隊頭。

過程

例如我們構造一個單調遞增的隊列會如下：

原序列為：

1
1 3 -1 -3 5 3 6 7

因為我們始終要維護隊列保證其 遞增 的特點，所以會有如下的事情發生：

操作 隊列狀態
1 入隊 {1}
3 比 1 大，3 入隊 {1 3}
-1 比隊列中所有元素小，所以清空隊列 -1 入隊 {-1}
-3 比隊列中所有元素小，所以清空隊列 -3 入隊 {-3}
5 比 -3 大，直接入隊 {-3 5}
3 比 5 小，5 出隊，3 入隊 {-3 3}
-3 已經在窗體外，所以 -3 出隊；6 比 3 大，6 入隊 {3 6}
7 比 6 大，7 入隊 {3 6 7}
例題參考代碼 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#define maxn 1000100
using namespace std;
int q[maxn], a[maxn];
int n, k;

void getmin() {  // 得到这个队列里的最小值，直接找到最后的就行了
  int head = 0, tail = -1;
  for (int i = 1; i < k; i++) {
    while (head <= tail && a[q[tail]] >= a[i]) tail--;
    q[++tail] = i;
  }
  for (int i = k; i <= n; i++) {
    while (head <= tail && a[q[tail]] >= a[i]) tail--;
    q[++tail] = i;
    while (q[head] <= i - k) head++;
    printf("%d ", a[q[head]]);
  }
}

void getmax() {  // 和上面同理
  int head = 0, tail = -1;
  for (int i = 1; i < k; i++) {
    while (head <= tail && a[q[tail]] <= a[i]) tail--;
    q[++tail] = i;
  }
  for (int i = k; i <= n; i++) {
    while (head <= tail && a[q[tail]] <= a[i]) tail--;
    q[++tail] = i;
    while (q[head] <= i - k) head++;
    printf("%d ", a[q[head]]);
  }
}

int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  getmin();
  printf("\n");
  getmax();
  printf("\n");
  return 0;
}

Ps. 此處的 "隊列" 跟普通隊列的一大不同就在於可以從隊尾進行操作，STL 中有類似的數據結構 deque。

例題 2 Luogu P2698 Flowerpot S

給出 \(N\) 滴水的座標，\(y\) 表示水滴的高度，\(x\) 表示它下落到 \(x\) 軸的位置。每滴水以每秒 1 個單位長度的速度下落。你需要把花盆放在 \(x\) 軸上的某個位置，使得從被花盆接着的第 1 滴水開始，到被花盆接着的最後 1 滴水結束，之間的時間差至少為 \(D\)。 我們認為，只要水滴落到 \(x\) 軸上，與花盆的邊沿對齊，就認為被接住。給出 \(N\) 滴水的座標和 \(D\) 的大小，請算出最小的花盆的寬度 \(W\)。\(1\leq N \leq 100000 , 1 \leq D \leq 1000000, 0 \leq x,y\leq 10^6\)

將所有水滴按照 \(x\) 座標排序之後，題意可以轉化為求一個 \(x\) 座標差最小的區間使得這個區間內 \(y\) 座標的最大值和最小值之差至少為 \(D\)。我們發現這道題和上一道例題有相似之處，就是都與一個區間內的最大值最小值有關，但是這道題區間的大小不確定，而且區間大小本身還是我們要求的答案。

我們依然可以使用一個遞增，一個遞減兩個單調隊列在 \(R\) 不斷後移時維護 \([L,R]\) 內的最大值和最小值，不過此時我們發現，如果 \(L\) 固定，那麼 \([L,R]\) 內的最大值只會越來越大，最小值只會越來越小，所以設 \(f(R) = \max[L,R]-\min[L,R]\)，則 \(f(R)\) 是個關於 \(R\) 的遞增函數，故 \(f(R)\geq D \implies f(r)\geq D,R\lt r \leq N\)。這説明對於每個固定的 \(L\)，向右第一個滿足條件的 \(R\) 就是最優答案。 所以我們整體求解的過程就是，先固定 \(L\)，從前往後移動 \(R\)，使用兩個單調隊列維護 \([L,R]\) 的最值。當找到了第一個滿足條件的 \(R\)，就更新答案並將 \(L\) 也向後移動。隨着 \(L\) 向後移動，兩個單調隊列都需及時彈出隊頭。這樣，直到 \(R\) 移到最後，每個元素依然是各進出隊列一次，保證了 \(O(n)\) 的時間複雜度。

參考代碼 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
typedef long long ll;
int mxq[N], mnq[N];
int D, ans, n, hx, rx, hn, rn;

struct la {
  int x, y;

  bool operator<(const la &y) const { return x < y.x; }
} a[N];

int main() {
  scanf("%d%d", &n, &D);
  for (int i = 1; i <= n; ++i) {
    scanf("%d%d", &a[i].x, &a[i].y);
  }
  sort(a + 1, a + n + 1);
  hx = hn = 1;
  ans = 2e9;
  int L = 1;
  for (int i = 1; i <= n; ++i) {
    while (hx <= rx && a[mxq[rx]].y < a[i].y) rx--;
    mxq[++rx] = i;
    while (hn <= rn && a[mnq[rn]].y > a[i].y) rn--;
    mnq[++rn] = i;
    while (L <= i && a[mxq[hx]].y - a[mnq[hn]].y >= D) {
      ans = min(ans, a[i].x - a[L].x);
      L++;
      while (hx <= rx && mxq[hx] < L) hx++;
      while (hn <= rn && mnq[hn] < L) hn++;
    }
  }
  if (ans < 2e9)
    printf("%d\n", ans);
  else
    puts("-1");
  return 0;
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Link-cute, Xeonacid, ouuan, Alphnia, Lyccrius
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用