Monotonic Queues

A monotonic queue answers minimum or maximum queries while a window slides through an array. It uses a deque of candidate indices: expired candidates leave the front, and candidates made permanently worse by a newer value leave the back. Every element is inserted and removed only a constant number of times, yielding linear total work. Unlike a priority queue, it does not keep every live value; it keeps exactly the candidates that could still win a future window. We will compute both the maximum and minimum in every fixed-length window.

Prerequisites: Queues and Deques, Monotonic Stacks, and basic window indexing.

Build the idea

1. 1. Define the moving question. For array [1,3,-1,-3,5,3,6,7] and k=3, the first window is positions 1..3 and has maximum 3. The next window is 2..4 and still has maximum 3; the third is 3..5 and has maximum 5. Scanning all k entries for each endpoint costs O(nk). A heap with lazy removal can solve it in O(n log n), but the monotonic deque exploits the fact that both endpoints move only forward and each query has the same window discipline.
2. 2. Store indices in increasing order. For maxima, keep candidate indices in the order they arrive, with their values strictly decreasing from front to back. The front therefore holds the largest candidate. Storing indices serves two purposes: it tells us when a candidate expires and lets us retrieve its value. A deque of values alone cannot distinguish two equal values inserted at different positions. On processing index i, the current window begins at i−k+1, so remove front indices ≤ i−k before answering.
3. 3. Remove dominated values from the back. While a[back] ≤ a[i], remove back. The newer i is at least as large and expires later, so that older candidate can never be a better maximum in any future window containing it. Any future window that still contains the older index and has endpoint at least i also contains i. This proves removal is safe, including equal values. Then append i. Values now decrease strictly, indices increase strictly, and all stored indices are in the current window. The maximum is a[front] once i≥k.
4. 4. Trace the critical transition. With k=3, after values 1 then 3, index 1 is removed as dominated by index 2. Reading -1 gives deque indices [2,3], representing [3,-1], so first maximum is 3. Reading -3 gives [2,3,4], maximum 3. Before adding 5 at index 5, index 2 expires; then 5 removes indices 4 and 3 from the back, leaving [5]. The maximum becomes 5. Expiration and domination are independent removal reasons: one uses time/position, the other uses value order.
5. 5. Compute minima symmetrically. For minima, keep increasing values and remove back entries while a[back] ≥ a[i]. The program holds two deques in the same scan. They share the same expiration rule but have opposite dominance inequalities. The first output line lists maxima, and the second lists minima. Each output position corresponds to one complete window in left-to-right order. We collect answers in vectors for readable printing; a streaming version could print immediately and avoid answer storage.
6. 6. Understand optimization limits. A monotonic deque can optimize some DP recurrences when candidate validity is a sliding interval and candidate scores do not change while stored. For example, dp[i]=cost[i]+min(dp[j]) for i−k≤j<i can keep candidate DP values in an increasing deque. In contrast, if a candidate's relative quality changes with i, simple domination may be invalid; convex hull techniques or segment trees may be needed. The method also does not answer arbitrary range queries in any order. Static arbitrary RMQ suggests sparse tables; updates with arbitrary ranges suggest segment trees.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<deque>
using namespace std;
void print(const vector<long long>&values){
    for(int i=0;i<static_cast<int>(values.size());++i){
        if(i){
            cout<<' ';
        }
        cout<<values[i];
    }
    cout<<'\n';
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    if(!(cin>>n>>k)||n<1||k<1||k>n){
        cout<<"INVALID\n";
        return 0;
    }
    vector<long long>a(n+1),maxima,minima;
    for(int i=1;i<=n;++i){
        cin>>a[i];
    }
    deque<int>maxQ,minQ; // Indices, not copied values.
    for(int i=1;i<=n;++i){
        // Positions before the current left boundary i-k+1 have expired.
        while(!maxQ.empty()&&maxQ.front()<=i-k){
            maxQ.pop_front();
        }
        while(!minQ.empty()&&minQ.front()<=i-k){
            minQ.pop_front();
        }
        // Newer equally good candidates expire later, so discard old ties.
        while(!maxQ.empty()&&a[maxQ.back()]<=a[i]){
            maxQ.pop_back();
        }
        while(!minQ.empty()&&a[minQ.back()]>=a[i]){
            minQ.pop_back();
        }
        // Candidate indices increase; maximum values decrease, minima increase.
        maxQ.push_back(i);
        minQ.push_back(i);
        if(i>=k){ // A complete length-k window now exists.
            maxima.push_back(a[maxQ.front()]);
            minima.push_back(a[minQ.front()]);
        }
    }
    print(maxima);
    print(minima);
}

Complexity analysis

Each index enters each deque once and leaves it at most once, from either end. Thus total processing is O(n), with amortized O(1) work per input item. A single item may cause many back removals, so individual steps need not be worst-case constant. Each deque holds at most k indices, using O(k) working memory. This implementation additionally stores the input and output arrays, so total storage is O(n). A streaming variant can reduce total storage to O(k).

Example input and output

Read n k with 1 ≤ k ≤ n, then n signed-64-bit values. Print all length-k window maxima, then all minima. No arithmetic on values is required, so every signed-64-bit input is supported. Invalid n or k prints INVALID.

Input

8 3
1 3 -1 -3 5 3 6 7

Output

3 3 5 5 6 7
-1 -3 -3 -3 3 3

There are 8−3+1=6 windows. Their maxima form the first line. Their minima form the second; for example, positions 5..7 contain [5,3,6], so their maximum is 6 and minimum is 3.

Practical applications

Use monotonic deques for sliding-window extrema, checking whether max−min stays within a threshold, and suitable bounded-transition DP. The technique also extends to variable-length windows whose left endpoint only moves forward. Related structures include monotonic stacks for one-sided nearest neighbors and sparse tables for static arbitrary range extrema.

Check your understanding

Why may an older value no greater than a new value be removed from a maximum deque?

Put it into practice

Find the longest subarray whose maximum minus minimum is at most a nonnegative limit L.