Задача

Дан массив a из N целых чисел. Для каждого из них надо найти ближайшее большее слева.

Алгоритм со стеком

Будем считать ответы по порядку, слева направо. Поддерживаем стек. Для каждого элемента удаляем из стека все элементы меньшие или равные ему. Затем, если стек не пуст, ответом для текущей позиции будет элемент на вершине стека. Добавляем текущее число в стек.

Алгоритм без стека

Заметим, что ответы для предыдущих чисел полностью задают стек. Уберём его.

Профит

• Памяти стало в 2 раза меньше.
• Время уменьшилось на 20% (по данным Ideone.com).
• Кода тоже стало меньше.

Код обеих версий

const int N = 4e7;
int a[N];
int link[N];
int stack[N];
int ptr = 0;
 
void with_stack() {
	fill_n(link, N, -1);
	for (int i = 0; i < N; ++i) {
		while (ptr > 0 && a[stack[ptr - 1]] <= a[i]) {
			--ptr;
		}
		if (ptr) {
			link[i] = stack[ptr - 1];
		}
		stack[ptr++] = i;
	}
}
 
void without_stack() {
	for (int i = 0; i < N; ++i) {
		int &l = link[i];
		l = i - 1;
		while (l >= 0 && a[l] <= a[i]) {
			l = link[l];
		}
	}		
}

Этот же код на Ideone (можно раскомментировать вызов одной из функций и посмотреть время работы)