Monotonic Stack

10 Aug 2025

1. Introduction

A Monotonic Stack is a problem-solving tool rather than an algorithm by itself.
In complex problems it normally handles one part of the work, such as processing data, rather than appearing alone.
Its template task is: for an element in a sequence, find the index of the first greater or smaller element to its left or right.

2. Implementation

For a sequence a of length n, define f(i) as the index of the first element after the i-th element that is greater than a[i]. If none exists, f(i) is 0. Find f(1…n).

Constraint: n ≤ 3 × 10⁶.


a[]: 1 4 2 3 5


f(): 2 5 4 5 0

Sample explanation:

When i = 1, a[i] = 1. The first greater value on its right is 4 at index 2, so f(1) = 2.
When i = 2, a[i] = 4. The first greater value on its right is 5 at index 5, so f(2) = 5.

Approach:

Use a vector to simulate the monotonic stack and an f array to store answers.
Process the sequence from right to left.
For each a[i], compare it with the stack top. If a[i] is greater, pop the top and continue until the top is greater than a[i] or the stack is empty.
If the stack is still nonempty, its top is the answer for a[i], namely f(i).
Push the index of the current element.

#include<bits/stdc++.h>
using namespace std;
int n;
int a[3000010];
int f[3000010];
vector<int> stk;
int main() {
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	for(int i = n; i >= 1; i--) {
		while(!stk.empty() && a[stk.back()] <= a[i])
			stk.pop_back();
		if(!stk.empty())
			f[i] = stk.back();
		stk.push_back(i);
	}
	for(int i = 1; i <= n; i++)
		cout << f[i] << " ";
	return 0;
}

Execution trace:

a[]:   1 4 2 3 5
index: 1 2 3 4 5

Process 5. The stack is empty, so neither while nor if runs; push 5. Nothing is to its right, hence f(5) = 0.
Process 3. The stack contains 5, which is greater than 3, so while does not run. The if statement assigns f(4) = 5; then push 3.
Process 2. The stack contains 3 and 5, with 3 on top. Since 3 is greater than 2, f(3) = 3; then push 2.
Process 4. The stack contains 2, 3, and 5. Since 4 is greater than the top 2, pop 2 and 3. The if statement assigns f(2) = 5; then push 4.
Process 1. The stack contains 4 and 5, with 4 on top. Since 4 is greater than 1, f(1) = 4.

Why it works:

While processing from right to left, deleting elements from the stack is the optimization. If the current element is greater than the top, pop the top. This is safe because for every still-unprocessed element to the left, the current value is both closer and greater, so the removed value can never be the first greater answer.

In the sample, processing 4 removes 2 and 3. For the later-processed value 1, 4 is closer and greater than both 2 and 3, so neither can be its answer.

Using a vector to simulate a monotonic stack is convenient for two reasons:

Elements can be accessed by index, such as vector[i], whereas stack exposes only its top.
STL functions such as sort and find can be used.

For convenience, the explanation above calls this “pushing an element.” In fact, the stack stores the element’s index because the problem asks for indices. Treat the stack top as an index, for example:

a[stk.back()]

3. Variations

Example 1: Luogu P2866

This is a simple variation: for each element, find the first greater element to its left. Use that greater element as the left boundary and the current element as the right boundary, then sum the resulting interval lengths.

Example 2: Luogu U478856

Task: for a sequence of length n, find the sum of the maximum values of all intervals.

This problem is slightly harder and cannot use the template directly. The key is: for every element, find the number of intervals for which it is the maximum. Let c[i] be that count for a[i]. The answer is Σ_{i = 1}ⁿ c_i × a_i. To obtain those counts, run a monotonic stack once from left to right and once from right to left. For each element, find the first greater element on both sides. This determines the maximal interval, from which the number of all valid intervals is calculated.

        4   8   3   5   7   1   9   6
            l           i       r
index   1   2   3   4   5   6   7   8

For the value 7 at position i = 5, the two passes give its maximal interval with exclusive boundaries l and r. Then c[i] = (i - l) * (r - i): i - l is the number of possible left endpoints and r - i the number of possible right endpoints. In this example, c[5] = (5 - 2) * (7 - 5) = 6.

Example 3 Luogu B4273

This is a two-dimensional monotonic-stack variation. As shown below, rectangles have equal base widths but different heights; given the heights, find the largest rectangle area.

This follows the same idea. For the highlighted bar, extend left and right until extension is impossible, producing the blue-framed rectangle. If the bar height is h, this gives the largest area of a rectangle with height h. Try every bar height and take the maximum.

For each height, use a monotonic stack to find the first smaller element on both sides. The interval length times the bar height is the maximum area for that height.


3 2 1 4 5 2

For other two-dimensional variations, use this problem as a foundation and try reducing the new task to it.

Monotonic Stack

Related Posts