Стек с функцией min

Сделать структуру данных аналогичную стеку (т.е. с обычными операциями push, pop и top) с поддержкой функции getMin — возвращает минимальный элемент среди тех, что есть на стеке.

Пример:

const st = new MinStack();

st.push(-2);
st.push(0);
st.push(-3);
// -3
st.getMin();
st.pop();
// 0
st.top();
// -2
st.getMin();

Решение

Сперва любопытно реализовать просто Stack (как конструктор объектов), а дальше действовать на его основе.

class Stack {
	constructor() {
		this._st = [];
	}
	push(val) {
		this._st.push(val);
	}
	pop() {
		return this._st.pop();
	}
	top() {
		return this._st[this._st.length - 1];
	}
	empty() {
		return this._st.length === 0;
	}
}

const st = new Stack();

Зачем нужна такая странная обёртка для массива? Резонный вопрос 😊

Дело в том, что у массива реализован оператор [] , а у данного объекта, т.е. стека — нет. Чтобы не было возможности достать элемент по индексу, раз по условию мы работаем со стеком.

Если наличие _ перед st не останавливает от использования приватного поля, можно пойти дальше и честно скрыть его.

function Stack() {
	const st = [];
	
	return {
		push(val) {
			st.push(val);
		},
		pop() {
			return st.pop();
		},
		top() {
			return st[st.length - 1];
		},
		empty() {
			return st.length === 0;
		}
	}
}

const st = new Stack();

<aside> 💡 В JavaScript функция-конструктор может возвращать новый объект явно.

</aside>

Итак, у нас есть стек, теперь надо, используя композицию или наследование, сделать MinStack с функцией getMin.

Решение «в лоб» — каждый раз при вызове функции getMin будем «разматывать» весь стек, доставая каждый элемент по очереди, запомним минимальный, и сложим все элементы назад.

function MinStack() {
	const st = new Stack();

	return Object.assign(st, {
		getMin() {
			const tmp = getStack();
			let min = st.top();
			
			// перекладываем текущий стек во временный —
			// стандартный способ обойти все элементы стека
			while (!st.empty()) {
				const top = st.pop();
				// находим минимальный элемент среди всех
				if (top < min) {
					min = top;
				}
				tmp.push(top);
			}
			// возвращаем всё обратно
			while (!tmp.empty()) {
				st.push(tmp.pop());
			}
			return min;
		}
	});
}

Сложность обычных методов стека, как и полагается, O(1), однако getMin работает за O(n) как по времени так и по памяти.

Не самый лучший вариант, можно ли сделать так, чтобы getMin работал за O(1) как и другие методы?

Ключ к решению — хранить минимальный на данный момент элемент на стеке, рядом с обычным, текущим элементом (или просто завести второй стек, для минимальных элементов)

function MinStack() {
	const st = new Stack();
	const minSt = new Stack();
	
	// копируем всё в новый, пустой объект
	return Object.assign({}, st, {
		push(val) {
			// аналог вызова super — просто добавим значение в стек, как обычно
			st.push(val);
			
			// если очередной элемент меньше того,
			// что уже на «стеке для минимумов»,
			// надо добавить новый минимум
			if (minSt.empty() || minSt.top() > st.top()) {
				minSt.push(st.top());

			// иначе минимум не меняется, но его всё равно надо положить на стек,
			// чтобы сохранить концепцию «минимумов на каждом уровне»:
			// размеры стеков должны быть синхронизированы
			} else {
				minSt.push(minSt.top());
			}
		},
		pop() {
			st.pop();
			minSt.pop();
		},
		getMin() {
			// за O(1) получаем актуальный минимум,
			// для данного состояния основного стека
			return minSt.top();
		}
	});
}

Для сравнения — LeetCode выдаёт следующие числа для обоих решений: