Найдите ближайшие меньшие числа слева в массиве

Дано: вам дан массив. Вы должны найти ближайший меньший элемент для каждого элемента, чтобы меньший элемент находился с левой стороны.

Если для определенного элемента слева нет меньшего элемента, верните для него -1.

E.g :

Input

A = [4, 5, 2, 10, 8]

Output

R = [-1, 4, -1, 2, 2]

Решение

Мы можем использовать стек для хранения элементов таким образом, что верхний элемент может быть меньшим элементом.

vector<int> prevSmaller(vector<int> &A) {
stack<int> s;
s.push(-1);
vector<int> result;
for(int i=0;i<A.size();i++){
while(!s.empty()&&s.top()>=A[i]){
s.pop();
}
result.push_back(s.top());
s.push(A[i]);
}
return result;
}

Сначала мы помещаем -1 в стек, потому что для первого элемента в массиве слева нет меньшего элемента. Следовательно, мы назначаем -1 для этого.

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

Вы можете увидеть визуализацию порядка исполнения.

ИТЕРАЦИЯ 1

текущий элемент -4

Как только вы начинаете итерацию, у нас есть первый элемент 4. В этом экземпляре стека есть только один элемент -1. Внутри цикла while мы будем проверять, не пуст ли стек и что верхний элемент стека больше текущего.

Здесь -1 уже меньше 4, следовательно, цикл while не выполняется, и мы получаем верхний элемент, а текущий элемент, т.е. 4, помещаем в стек.

ИТЕРАЦИЯ2

текущий элемент — 5

Внутри цикла while во 2-й итерации верхний элемент, т.е. 4, уже меньше 5. Следовательно, цикл while не выполняется и возвращает верхний элемент, т.е. 4.

и мы помещаем текущий элемент 5 в стек. (См. визуализацию выше)

ИТЕРАЦИЯ3

текущий элемент — 2

Поскольку стек не пуст, а верхний элемент стека больше и равен текущему элементу 2. Итак, этот цикл while будет выполняться, и мы извлекаем верхний элемент из стека, пока не получим верхний элемент меньше, чем текущий элемент (2).

мы возвращаем -1 и помещаем текущий элемент (2) в стек.

ИТЕРАЦИЯ4

текущий элемент — 10

в то время как условие здесь не выполняется, потому что верхний элемент (2) меньше текущего элемента (10).

Следовательно, мы возвращаем 2 и возвращаем текущий элемент (10) обратно в стек.

ИТЕРАЦИЯ5

текущий элемент — 8

В этом случае верхний элемент (10) больше 8, поэтому цикл while будет выполняться и выталкивать верхние элементы, пока мы не получим меньший элемент, чем текущий элемент (8).

Итак, мы возвращаем 2 в результате и помещаем текущий элемент 8 в стек.

Наконец все итерации будут завершены.

Все результаты сохраняются в массиве результатов.