Card 03/ 08
The Monotonic Stack Template in Python, Java and TypeScript
One loop over the positions, one inner loop that pops and answers, and one push.
The monotonic stack template is one loop over the positions, an inner loop that pops every waiting position the current value beats, and a push. Two lines change between variants, and the highlighted lines mark them: the comparison, which decides between greater and smaller, and what is recorded when an index is popped, a value or a distance. The answer array starts filled with −1, the answer for a position that is never popped. Each listing runs on 4 1 6 2 3 5, on falling values and on an empty array.
The next greater template in three languages
def next_greater(values: list[int]) -> list[int]:
answer = [-1] * len(values)
stack: list[int] = []
for i, value in enumerate(values):
while stack and values[stack[-1]] < value:
answer[stack.pop()] = value
stack.append(i)
return answer
for values in [[4, 1, 6, 2, 3, 5], [5, 4, 3], []]:
print(f"{values} next greater {next_greater(values)}")[4, 1, 6, 2, 3, 5] next greater [6, 6, -1, 3, 5, -1]
[5, 4, 3] next greater [-1, -1, -1]
[] next greater []import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
public class NextGreater {
static int[] nextGreater(int[] values) {
int[] answer = new int[values.length];
Arrays.fill(answer, -1);
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < values.length; i++) {
while (!stack.isEmpty() && values[stack.peek()] < values[i]) {
answer[stack.pop()] = values[i];
}
stack.push(i);
}
return answer;
}
public static void main(String[] args) {
int[][] inputs = {{4, 1, 6, 2, 3, 5}, {5, 4, 3}, {}};
for (int[] values : inputs) {
System.out.println(Arrays.toString(values) + " next greater " + Arrays.toString(nextGreater(values)));
}
}
}[4, 1, 6, 2, 3, 5] next greater [6, 6, -1, 3, 5, -1]
[5, 4, 3] next greater [-1, -1, -1]
[] next greater []function nextGreater(values: number[]): number[] {
const answer: number[] = new Array(values.length).fill(-1);
const stack: number[] = [];
for (let i = 0; i < values.length; i++) {
while (stack.length > 0 && values[stack.at(-1)!] < values[i]) {
answer[stack.pop()!] = values[i];
}
stack.push(i);
}
return answer;
}
const inputs: number[][] = [[4, 1, 6, 2, 3, 5], [5, 4, 3], []];
for (const values of inputs) {
console.log(`[${values.join(", ")}] next greater [${nextGreater(values).join(", ")}]`);
}[4, 1, 6, 2, 3, 5] next greater [6, 6, -1, 3, 5, -1]
[5, 4, 3] next greater [-1, -1, -1]
[] next greater []The three listings print the same answers, and on falling values nothing is ever popped, so every answer stays −1. The pass is O(n) time and O(n) extra space for n values.
Python uses a list with append and pop, and TypeScript an array with push, pop and at(-1) to read the top. Java uses ArrayDeque with push, pop and peek, not the older Stack class, which extends Vector and locks on every call. Reversing the comparison, > in place of <, finds the next smaller value instead.
← → move through sections and cards