Monotone Queue

Introduction

Before learning about monotone queues, let us first look at an example problem.

The brute-force idea is simple: for each sequence $i \sim i+k-1$, compare its values one by one to find the maximum (and minimum), with time complexity about $O(n \times k)$.

Clearly, this performs a great deal of repeated work. Except for the first $k-1$ and last $k-1$ values, every value is compared $k$ times. Since $100\%$ of the test data has $n \le 1000000$, this will obviously TLE when $k$ is large.

This is where the monotone queue is useful.

Definition

As its name suggests, a monotone queue has two key features: “monotone” and “queue”.

“Monotone” refers to the pattern of its elements—either increasing or decreasing.

“Queue” means that elements can be operated on only at the front and the back.

P.S. The “queue” in a monotone queue differs somewhat from an ordinary queue, as we will see shortly.

Example analysis

Explanation

With the concept of a monotone queue above, it is natural to optimize the problem using one.

We need the maximum (or minimum) of every consecutive $k$ values. When a value enters the range whose maximum is being sought, if it is greater than a value already ahead of it in the queue, that earlier value will leave the queue first and can no longer be the maximum.

In other words, when this condition holds, pop the earlier values and then push the new value onto the back of the queue.

This maintains a decreasing queue and reduces repeated comparisons. Moreover, because the maintained queue contains exactly the candidates in the query range and is decreasing, its front is necessarily the maximum in that range, so outputting the front is enough.

Clearly, each value enters and leaves the queue exactly once, reducing the time complexity to $O(n)$.

Because the query interval has fixed length, even a large value outside the query window cannot be output. We therefore also need a site array recording the position of the value at position $i$ in the queue in the original array, so that an out-of-range front can be removed.

Process

For example, constructing an increasing monotone queue proceeds as follows:

The original sequence is:

1 3 -1 -3 5 3 6 7

Because we always maintain the queue so that it remains increasing, the following occurs (assume $k = 3$):

#include <cstdlib>
#include <cstring>
#include <iostream>
constexpr int MAXN = 1000100;
using namespace std;
int q[MAXN], a[MAXN];
int n, k;

void getmin() {  // Obtain the minimum of this queue; it is at the back
  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() {  // The maximum is handled analogously
  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;
}

P.S. The main difference between this “queue” and an ordinary queue is that it supports operations at the back as well. The STL has a similar data structure, deque.

After sorting all drops by their $x$-coordinates, the problem becomes finding an interval with the smallest difference in $x$-coordinates such that the difference between the maximum and minimum $y$-coordinates in the interval is at least $D$. This resembles the previous problem because both involve the maximum and minimum in an interval, but here the interval length is unknown and is itself the answer.

We can still use one increasing and one decreasing monotone queue, moving $R$ rightward while maintaining the maximum and minimum in $[L,R]$. For fixed $L$, the maximum in $[L,R]$ only increases and the minimum only decreases, so if $f(R) = \max[L,R]-\min[L,R]$, then $f(R)$ is increasing in $R$. Therefore, $f(R)\geq D \implies f(r)\geq D,R\lt r \leq N$. For each fixed $L$, the first $R$ to the right satisfying the condition is optimal. So the overall procedure is to fix $L$, move $R$ from left to right, and use two monotone queues to maintain the extrema in $[L,R]$. Once the first valid $R$ is found, update the answer and move $L$ rightward as well. As $L$ advances, remove outdated fronts from both queues. Until $R$ reaches the end, each element still enters and leaves each queue once, giving $O(n)$ time complexity.

#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;
}