Skip to content

Monotonic Queue

Introduction

Before learning about monotonic queues, let's first look at an example problem.

Example Problem

Sliding Window

The general idea of this problem is to give an array of length \(n\) and output the maximum and minimum values in every consecutive segment of \(k\) numbers.

The most brute-force approach is straightforward: for each segment \(i \sim i+k-1\), compare each element to find the maximum (and minimum). The time complexity is approximately \(O(n \times k)\).

Clearly, this involves a lot of redundant work. Except for the first \(k-1\) and last \(k-1\) numbers, each number is compared \(k\) times. For \(100\%\) of the data in the problem, \(n \le 1000000\). When \(k\) is relatively large, this will obviously lead to TLE.

This is where monotonic queues come into play.

Definition

As the name suggests, the key points of a monotonic queue are "monotonic" and "queue".

  • "Monotonic" refers to the "pattern" of the elements—increasing (or decreasing).
  • "Queue" means that elements can only be operated on from the front and the rear.

Ps. The "queue" in a monotonic queue is somewhat different from a normal queue, which will be explained later.

Example Analysis

Explanation

With the concept of a "monotonic queue" in mind, it's easy to think of using it for optimization.

We are asked to find the maximum (or minimum) value in every consecutive segment of \(k\) numbers. Clearly, when a number enters the range where we are "searching" for the maximum value, if this number is larger than the numbers before it (which entered the queue earlier), then those earlier numbers will leave the queue before this number and can no longer be the maximum.

In other words—when the above condition is satisfied, we can "pop" the preceding numbers and then truly push the current number into the rear of the queue.

This is equivalent to maintaining a decreasing queue, which aligns with the definition of a monotonic queue. It reduces the number of redundant comparisons. Moreover, since the maintained queue is within the query range and is decreasing, the front of the queue must be the maximum value in that query range. Therefore, we only need to output the front element.

Obviously, in this algorithm, each number enters and leaves the queue only once, so the time complexity is reduced to \(O(n)\).

Since the query interval length is fixed, values outside the query range cannot be output even if they are large. Therefore, we also need a site array to record the position of the \(i\)-th element in the queue within the original array, so that we can pop the front element when it goes out of bounds.

Process

For example, if we construct a monotonically increasing queue, the process would be as follows:

The original sequence is:

1
1 3 -1 -3 5 3 6 7

Because we always maintain the queue to ensure its increasing property, the following events occur (assuming \(k = 3\)):

Operation Queue State
1 enters the queue {1}
3 is larger than 1, 3 enters {1 3}
-1 is smaller than all elements, clear queue, -1 enters {-1}
-3 is smaller than all elements, clear queue, -3 enters {-3}
5 is larger than -3, directly enters {-3 5}
3 is smaller than 5, 5 leaves, 3 enters {-3 3}
-3 is outside the window, so -3 leaves; 6 is larger than 3, 6 enters {3 6}
7 is larger than 6, 7 enters {3 6 7}
Example Reference Code 
 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 <cstdlib>
#include <cstring>
#include <iostream>
constexpr int MAXN = 1000100;
using namespace std;
int q[MAXN], a[MAXN];
int n, k;

void getmin() {  // Get the minimum value in the queue, directly find the last one
  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++;
    cout << a[q[head]] << ' ';
  }
}

void getmax() {  // Same principle as above
  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++;
    cout << a[q[head]] << ' ';
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> k;
  for (int i = 1; i <= n; i++) cin >> a[i];
  getmin();
  cout << '\n';
  getmax();
  cout << '\n';
  return 0;
}

Ps. One major difference between this "queue" and a normal queue is that operations can be performed at the rear. STL has a similar data structure called deque.

Example 2 Luogu P2698 Flowerpot S

Given the coordinates of \(N\) water droplets, \(y\) represents the height of the droplet, and \(x\) represents its falling position on the x-axis. Each droplet falls at a speed of 1 unit length per second. You need to place a flowerpot at some position on the x-axis so that the time difference between the first droplet caught by the flowerpot and the last droplet caught is at least \(D\). We consider a droplet caught as long as it lands on the x-axis and aligns with the edge of the flowerpot. Given the coordinates of \(N\) droplets and the value of \(D\), calculate the minimum width \(W\) of the flowerpot. \(1\leq N \leq 100000 , 1 \leq D \leq 1000000, 0 \leq x,y\leq 10^6\)

After sorting all droplets by their \(x\) coordinates, the problem can be transformed into finding an interval with the smallest \(x\) coordinate difference such that the difference between the maximum and minimum \(y\) coordinates in this interval is at least \(D\). We notice that this problem is similar to the previous example in that both involve the maximum and minimum values within an interval. However, in this problem, the interval size is not fixed, and the interval size itself is the answer we are seeking.

We can still use one increasing and one decreasing monotonic queue to maintain the maximum and minimum values within \([L,R]\) as \(R\) moves backward. However, we now realize that if \(L\) is fixed, the maximum value in \([L,R]\) will only increase, and the minimum will only decrease. So let \(f(R) = \max[L,R]-\min[L,R]\). Then \(f(R)\) is an increasing function of \(R\), so \(f(R)\geq D \implies f(r)\geq D,R\lt r \leq N\). This means that for each fixed \(L\), the first \(R\) to the right that satisfies the condition is the optimal answer. Thus, the overall solution process is: first fix \(L\), move \(R\) from front to back, and use two monotonic queues to maintain the extreme values in \([L,R]\). When the first \(R\) satisfying the condition is found, update the answer and move \(L\) backward as well. As \(L\) moves backward, both monotonic queues need to promptly pop the front element. This way, until \(R\) reaches the end, each element still enters and leaves the queue only once, ensuring \(O(n)\) time complexity.

Reference Code 
 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 <algorithm>
#include <iostream>
using namespace std;
constexpr int N = 100005;
using ll = long long;
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() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> D;
  for (int i = 1; i <= n; ++i) cin >> 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)
    cout << ans << '\n';
  else
    cout << "-1\n";
  return 0;
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用