Monotonic stack

A monotonic stack finds, for every element of an array, the nearest greater (or smaller) element to its right or left, in $O(n)$ for the whole array. It is a stack of positions whose values stay sorted, and it also finds the largest rectangle in a histogram. If you need the minimum of every window of fixed length, use a monotonic queue instead.

Explanation

Here are 8 buildings in a row, with heights 2, 7, 3, 1, 5, 4, 6 and 2 at positions 0 to 7. For each building, which is the first taller building to its right? Look at position 2, of height 3. The building of height 1 next to it is lower, and the next one, of height 5 at position 4, is taller. The answer for position 2 is 5, the blue arrow in Fig. 1.

Fig. 1. The blue arrow points to the first taller building to the right of position 2. The red arrow points to the tallest building to its right.

The direct way is to walk right from each building until something taller appears. It is correct, and on this street it takes 14 comparisons. But on a street where every building is lower than the one before it, every walk goes to the end: n(n-1)/2 comparisons. For n = 10^5 buildings that is too slow.

Instead, scan once from right to left and remember what we've seen. The natural thing to remember is the tallest building so far. At position 2 it says 6, the red arrow. But the building of height 5 is nearer and still taller than 3.

We need to keep several candidates. When the scan reaches a building, look at the buildings to its right that are not taller than it. None of them can ever be the answer for a building further left: the new building is nearer and at least as tall, so it blocks the view. They can be thrown away for good. What stays, read from the nearest, gets taller and taller, and we only add and remove at the nearest end. That is a stack, with the nearest building on top.

For each new building, from right to left, there are three moves:

1. Pop every building from the top that is not taller than the new one.

2. Read the top: it is the answer. If the stack is empty, there is no answer.

3. Push the new building.

Check it on position 2. When the building of height 3 arrives, the stack holds heights 1, 5 and 6 from the top. The 1 is popped, and the 5 on top is the answer.

There is a while loop inside the scan, but each position is pushed once and popped at most once, so all the pops together are at most $n$. That is at most $2n$ stack operations, $O(n)$.

The values in the stack always increase from the top to the bottom here, so this is called a monotonic stack. Each building is an element of the array, drawn as a bar, and the first taller one to its right is its next greater element. Fig. 2 runs the scan on all eight bars.

The scan starts at the right end: position 7, value 2, is the new element (outlined). The stack below is empty.

The stack is empty, so position 7 has no next greater element: the answer is −1, written above the element.

push(7): 2 goes on top of the stack, at the right end. Elements in the stack are light blue.

Position 6, value 6, is the new element.

2 at position 7 is not greater than 6, so pop() removes it from the top of the stack; it turns grey, because it can never be an answer again.

The stack is empty, so position 6 has no next greater element: the answer is −1.

push(6): 6 goes on top of the stack, at the right end.

Position 5, value 4, is the new element.

The top of the stack, 6 at position 6, is greater than 4, so it is the answer for position 5.

push(5): 4 goes on top of the stack, at the right end.

Position 4, value 5, is the new element.

4 at position 5 is not greater than 5, so pop() removes it from the top of the stack.

The top of the stack, 6 at position 6, is greater than 5, so it is the answer for position 4.

push(4): 5 goes on top of the stack, at the right end.

Position 3, value 1, is the new element.

The top of the stack, 5 at position 4, is greater than 1, so it is the answer for position 3.

push(3): 1 goes on top of the stack, at the right end.

Position 2, value 3, is the new element.

1 at position 3 is not greater than 3, so pop() removes it from the top of the stack.

The top of the stack, 5 at position 4, is greater than 3, so it is the answer for position 2.

push(2): 3 goes on top of the stack, at the right end.

Position 1, value 7, is the new element.

3 at position 2 is not greater than 7, so pop() removes it from the top of the stack.

5 at position 4 is not greater than 7, so pop() removes it from the top of the stack.

6 at position 6 is not greater than 7, so pop() removes it from the top of the stack.

The stack is empty, so position 1 has no next greater element: the answer is −1.

push(1): 7 goes on top of the stack, at the right end.

Position 0, value 2, is the new element.

The top of the stack, 7 at position 1, is greater than 2, so it is the answer for position 0.

push(0): 2 goes on top of the stack, at the right end.

Done. The answers are 7, −1, 5, 5, 6, 6, −1, −1. There were 8 pushes and 6 pops, 14 stack operations, at most 2n = 16.

1/31

Fig. 2. Step through the scan with the buttons or the arrow keys. The stack is below the bars, with its top on the right. A blue arrow points from the new bar to its next greater element.

Expect this technique when $n$ is up to 10^5 or 10^6 and the problem asks this for every element.

In C++

The stack stores positions i, not values, because many problems print positions and the histogram below needs widths, and reads a value as a[st.top()]. The array nxt keeps the answer: nxt[i] is the position of the next greater element of a[i], or -1 if there is none.

The program reads n and then n numbers, and prints for each element the next strictly greater value, or -1. For the array from Fig. 1, the input is:

8
2 7 3 1 5 4 6 2

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    vector<int> nxt(n, -1);   // position of the next greater element, -1 if none
    stack<int> st;            // positions; their values increase from top to bottom
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && a[st.top()] <= a[i]) st.pop();   // pop
        if (!st.empty()) nxt[i] = st.top();                     // read
        st.push(i);                                             // push
    }

    for (int i = 0; i < n; i++) {
        cout << (nxt[i] == -1 ? -1 : a[nxt[i]]) << (i + 1 < n ? ' ' : '\n');
    }
}

The stack and nxt take $O(n)$ memory.

The same three moves find all four kinds of nearest element. Only the direction of the scan and the pop condition change:

For "greater or equal" or "smaller or equal", drop the = from the pop condition, so that equal values stay in the stack as answers.

Largest rectangle in a histogram

Read the array from Fig. 1 as a histogram: bars of width 1 and heights 2, 7, 3, 1, 5, 4, 6, 2. What is the largest rectangle that fits under the bars? Any such rectangle has a lowest bar i, and its height is a[i]. It can spread left and right until it meets a bar smaller than a[i]. The first smaller bar on the left is the previous smaller element L[i], found by a scan from left to right. The first smaller bar on the right is the next smaller element R[i], found by a scan from right to left. When there is no smaller bar, L[i] = -1 and R[i] = n, just outside the array. Bars equal to a[i] are popped in both scans, so the rectangle spreads over them too.

When bar 5, of height 4, arrives in the scan from the left, the stack holds bars 4 (height 5) and 3 (height 1), from the top. Bar 4 is not smaller, so it is popped, and bar 3 on top gives L[5] = 3. When it arrives in the scan from the right, the stack holds bars 6 (height 6) and 7 (height 2). Bar 6 is popped, and R[5] = 7.

Fig. 3. The blue rectangle, area 12, is the largest. The red one uses the full width at height 1: area 8. The table gives each bar's rectangle.

Fig. 4 shows bar 5's rectangle: it covers bars 4 to 6 at height 4, so its area is 4 · 3 = 12.

vector<int> L(n, -1), R(n, n);
stack<int> st;
for (int i = 0; i < n; i++) {                     // previous smaller: L[i]
    while (!st.empty() && a[st.top()] >= a[i]) st.pop();   // pop
    if (!st.empty()) L[i] = st.top();                       // read
    st.push(i);                                             // push
}
st = stack<int>();                                // empty the stack
for (int i = n - 1; i >= 0; i--) {                // next smaller: R[i]
    while (!st.empty() && a[st.top()] >= a[i]) st.pop();   // pop
    if (!st.empty()) R[i] = st.top();                       // read
    st.push(i);                                             // push
}
long long best = 0;
for (int i = 0; i < n; i++) {
    best = max(best, a[i] * (R[i] - L[i] - 1));
}

There are three passes of $O(n)$, so the whole computation is $O(n)$ time and memory.

Common mistakes

• Using the wrong comparison for equal values. On the array 3, 3, popping while a[st.top()] < a[i] leaves the equal 3 on top and prints 3 -1 instead of -1 -1 for the strictly greater element.

• Reusing the stack for the second scan without emptying it. Positions left over from the first scan become false answers: on heights 1, 3, 3 the next smaller scan sets R[1] = R[2] = 0, and the program prints 3 instead of 6. Reset it with st = stack<int>(); or declare a new stack.

Similar techniques

A monotonic queue finds the minimum or maximum of every window of fixed length. Positions also leave from the front when they fall out of the window, so it is kept in a deque.

A sparse table answers the minimum of any range given in a query on a fixed array. Use it when the queries give the ranges. A segment tree does the same when the array changes.

Practice