Дано: вам дан массив. Вы должны найти ближайший меньший элемент для каждого элемента, чтобы меньший элемент находился с левой стороны.
Если для определенного элемента слева нет меньшего элемента, верните для него -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 в стек.
Наконец все итерации будут завершены.
Все результаты сохраняются в массиве результатов.