По заданному массиву найдите следующий меньший элемент для каждого элемента.
По заданному массиву найдите следующий меньший элемент в массиве для каждого элемента без изменения исходного порядка элементов.
Например, предположим, что данный массив равен 4,2,1,5,3.
Результирующий массив будет 2,1,-1,3,-1.
Мне задали этот вопрос в интервью, но я не мог придумать решение лучше, чем тривиальное решение O(n^2). Любой подход, который я мог придумать, то есть создание бинарного дерева поиска или сортировка массива, исказит исходный порядок элементов и, следовательно, приведет к неверному результату.
Любая помощь будет высоко оценен.
13 ответов
O(N) Алгоритм
- Инициализируйте выходной массив всем -1 с.
- Создайте пустой стек индексов элементов, которые мы посетили во входном массиве, но еще не знаем ответ для него в выходном массиве.
- Итерация по каждому элементу во входном массиве:
- Это меньше, чем предмет, проиндексированный на вершине стека?
- Да. Это первый такой элемент, который будет таким. Заполните соответствующий элемент в нашем выходном массиве, удалите элемент из стека и повторите попытку, пока стек не станет пустым или ответ будет отрицательным.
- Продолжайте до 3.2.
- Добавьте этот индекс в стек. Продолжайте итерацию с 3.
- Это меньше, чем предмет, проиндексированный на вершине стека?
Реализация Python
def find_next_smaller_elements(xs):
ys=[-1 for x in xs]
stack=[]
for i,x in enumerate(xs):
while len(stack)>0 and x<xs[stack[-1]]:
ys[stack.pop()]=x
stack.append(i)
return ys
>>> find_next_smaller_elements([4,2,1,5,3])
[2, 1, -1, 3, -1]
>>> find_next_smaller_elements([1,2,3,4,5])
[-1, -1, -1, -1, -1]
>>> find_next_smaller_elements([5,4,3,2,1])
[4, 3, 2, 1, -1]
>>> find_next_smaller_elements([1,3,5,4,2])
[-1, 2, 4, 2, -1]
>>> find_next_smaller_elements([6,4,2])
[4, 2, -1]
объяснение
Как это устроено
Это работает, потому что всякий раз, когда мы добавляем элемент в стек, мы знаем, что его значение уже больше или равно каждому элементу в стеке. Когда мы посещаем элемент в массиве, мы знаем, что если он ниже, чем какой-либо элемент в стеке, он должен быть ниже, чем последний элемент в стеке, поскольку последний элемент должен быть самым большим. Поэтому нам не нужно выполнять какой-либо поиск в стеке, мы можем просто рассмотреть последний элемент.
Примечание. Вы можете пропустить шаг инициализации, если добавляете последний шаг для очистки стека и используете каждый оставшийся индекс, чтобы установить соответствующий элемент выходного массива в -1. В Python проще инициализировать его до -1 с при его создании.
Сложность времени
Это O(N). Основной цикл явно посещает каждый индекс один раз. Каждый индекс добавляется в стек ровно один раз и удаляется не более одного раза.
Решение как вопрос интервью
Этот вопрос может быть довольно пугающим в интервью, но я хотел бы отметить, что (надеюсь) интервьюер не будет ожидать, что решение возникнет из вашего ума полностью сформированным. Обсудите их через ваш мыслительный процесс. Мой пошел примерно так:
- Есть ли какая-то связь между позициями чисел и их следующим меньшим числом в массиве? Знание некоторых из них ограничивает то, что другие могут быть?
- Если бы я находился перед доской, я бы, вероятно, набросал примерный массив и нарисовал линии между элементами. Я мог бы также нарисовать их в виде 2D гистограммы - горизонтальная ось - это позиция во входном массиве, а вертикальная ось - это значение.
- У меня была догадка, это показало бы образец, но никакой бумаги, чтобы вручить. Я думаю, что диаграмма сделает это очевидным. Тщательно обдумав это, я увидел, что линии не будут произвольно перекрываться, а будут только гнездиться.
- Примерно в этот момент мне пришло в голову, что это невероятно похоже на алгоритм, который Python использует внутри для преобразования отступов в виртуальные токены INDENT и DEDENT, о которых я читал ранее. Смотрите "Как компилятор разбирает отступ?" на этой странице: http://www.secnetix.de/olli/Python/block_indentation.hawk Однако до тех пор, пока я фактически не разработал алгоритм, я продолжил эту мысль и определил, что это на самом деле то же самое так что я не думаю, что это слишком помогло. Тем не менее, если вы видите сходство с какой-то другой проблемой, которую вы знаете, вероятно, стоит упомянуть об этом и сказать, насколько она похожа и чем отличается.
- Отсюда общая форма алгоритма на основе стека стала очевидной, но мне все еще нужно было подумать об этом немного больше, чтобы быть уверенным, что он будет работать нормально для тех элементов, у которых нет последующих меньших элементов.
Даже если вы не придумали работающий алгоритм, постарайтесь дать интервьюеру понять, о чем вы думаете. Зачастую им интересен не только ответ, но и мыслительный процесс. Для сложной проблемы неспособность найти лучшее решение, но понимание проблемы может быть лучше, чем знание готового ответа, но неспособность дать ему много. анализ.
Начните делать BST, начиная с конца массива. Для каждого значения "v" ответом будет последний узел "Право", который вы взяли на пути к вставке "v", который вы можете легко отслеживать в рекурсивной или итеративной версии.
ОБНОВИТЬ:
Исходя из ваших требований, вы можете подходить к этому линейно:
Если каждый следующий элемент меньше текущего элемента (например, 6 5 4 3 2 1), вы можете обрабатывать его линейно, не требуя дополнительной памяти. Интересный случай возникает, когда вы начинаете получать перемешанные элементы (например, 4 2 1 5 3), и в этом случае вам нужно помнить их порядок до тех пор, пока вы не получите их "меньшие аналоги". Простой подход на основе стека выглядит следующим образом:
Вставьте первый элемент (a[0]) в стек.
Для каждого следующего элемента a[i] вы заглядываете в стек, и если значение ( peek()) больше, чем в руке a[i], вы получаете следующее меньшее число для этого элемента стека (peek()) { и продолжайте выталкивать элементы, пока peek() > a[i] }. Вытащите их и распечатайте / сохраните соответствующее значение. в противном случае просто вставьте свой a[i] в стек.
В конце стека будут содержаться те элементы, которые никогда не имели значения меньше их (справа от них). Вы можете заполнить -1 для них в вашем выходе.
например, А =[4, 2, 1, 5, 3];
stack: 4
a[i] = 2, Pop 4, Push 2 (you got result for 4)
stack: 2
a[i] = 1, Pop 2, Push 1 (you got result for 2)
stack: 1
a[i] = 5
stack: 1 5
a[i] = 3, Pop 5, Push 3 (you got result for 5)
stack: 1 3
1,3 don't have any counterparts for them. so store -1 for them.
Предполагая, что вы имели в виду первый следующий элемент, который ниже текущего элемента, вот 2 решения:
- использование
sqrt(N)сегментация. Разделите массив наsqrt(N)сегменты с длиной каждого сегментаsqrt(N), Для каждого сегмента рассчитайте его минимальный элемент, используя цикл. Таким образом, вы предварительно рассчитали минимальный элемент каждого сегмента вO(N), Теперь для каждого элемента следующий нижний элемент может находиться в том же сегменте, что и один, или в любом из последующих сегментов. Итак, сначала проверьте все последующие элементы в текущем сегменте. Если все больше, то переберите все последующие сегменты, чтобы выяснить, у кого элемент меньше, чем у текущего элемента. Если вы не смогли найти, результат будет-1, В противном случае, проверьте каждый элемент этого сегмента, чтобы узнать, что является первым элементом ниже текущего элемента. В целом, сложность алгоритмаO(N*sqrt(N))или жеO(N^1.5),
Вы можете достичь O(NlgN) используя сегментное дерево с аналогичным подходом.
- Сначала сортируйте массив по возрастанию (сохраняя исходное положение элементов в качестве спутниковых данных). Теперь, предполагая, что каждый элемент массива различен, для каждого элемента нам нужно будет найти самую низкую исходную позицию в левой части этого элемента. Это классическая проблема RMQ (Range Min Query), которая может быть решена разными способами, включая
O(N)один. Как мы должны отсортировать в первую очередь, общая сложностьO(NlogN), Вы можете узнать больше о RMQ из учебника TopCoder.
По некоторым причинам мне легче рассуждать о "предыдущем меньшем элементе", то есть "всех ближайших меньших элементах". Таким образом, применение в обратном направлении дает "следующий меньший".
Для записи, реализация Python за время O(n), пространство O(1) (т.е. без стека), поддерживающее отрицательные значения в массиве:
def next_smaller(l):
""" Return positions of next smaller items """
res = [None] * len(l)
for i in range(len(l)-2,-1,-1):
j=i+1
while j is not None and (l[j] > l[i]):
j = res[j]
res[i] = j
return res
def next_smaller_elements(l):
""" Return next smaller items themselves """
res = next_smaller(l)
return [l[i] if i is not None else None for i in res]
Сложность времени O(N), космическая сложность O(N).
Чистое решение на Java, сохраняющее порядок массива:
public static int[] getNGE(int[] a) {
var s = new Stack<Pair<Integer, Integer>>();
int n = a.length;
var result = new int[n];
s.push(Pair.of(0, a[0]));
for (int i = 1; i < n; i++) {
while (!s.isEmpty() && s.peek().v2 > a[i]) {
var top = s.pop();
result[top.v1] = a[i];
}
s.push(Pair.of(i, a[i]));
}
while (!s.isEmpty()) {
var top = s.pop();
result[top.v1] = -1;
}
return result;
}
static class Pair<K, V> {
K v1;
V v2;
public static <K, V> Pair<K, V> of (K v1, V v2) {
Pair p = new Pair();
p.v1 = v1;
p.v2 = v2;
return p;
}
}
Вот код JavaScript. Это видео объясняет Альго лучше
function findNextSmallerElem(source){
let length = source.length;
let outPut = [...Array(length)].map(() => -1);
let stack = [];
for(let i = 0 ; i < length ; i++){
let stackTopVal = stack[ stack.length - 1] && stack[ stack.length - 1].val;
// If stack is empty or current elem is greater than stack top
if(!stack.length || source[i] > stackTopVal ){
stack.push({ val: source[i], ind: i} );
} else {
// While stacktop is greater than current elem , keep popping
while( source[i] < (stack[ stack.length - 1] && stack[ stack.length - 1].val) ){
outPut[stack.pop().ind] = source[i];
}
stack.push({ val: source[i], ind: i} );
}
}
return outPut;
}
Выход -
findNextSmallerElem([98,23,54,12,20,7,27])
[23, 12, 12, 7, 7, -1, -1]
Вы можете решить это в O(n) времени выполнения с O(n) пространственной сложностью. Начните со стека и продолжайте толкать элементы, пока не найдете arr[i] такой, что arr[i] Фрагмент кода:vector<int> findNext(vector<int> values) {
stack<int> st;
vector<int> nextSmall(values.size(), -1);
st.push(0);
for (int i = 1; i < values.size(); i++) {
while (!st.empty() && values[i] < values[st.top()]) {
// change values[i] < values[st.top()] to values[i] > values[st.top()] to find the next greater element.
nextSmall[st.top()] = i;
st.pop();
}
st.push(i);
}
return nextSmall;
}
Вот наблюдение, которое, я думаю, можно превратить в решение O(n log n). Предположим, у вас есть ответ для последних k элементов массива. Что вам нужно для того, чтобы выяснить значение элемента непосредственно перед этим? Вы можете думать о последних k элементах как о разделенных на серию диапазонов, каждый из которых начинается с некоторого элемента и продолжается до тех пор, пока не достигнет меньшего элемента. Эти диапазоны должны быть в порядке убывания, поэтому вы можете подумать о том, чтобы выполнить бинарный поиск по ним, чтобы найти первый интервал, меньший, чем этот элемент. Затем вы можете обновить диапазоны, чтобы учесть этот новый элемент.
Теперь, как лучше всего это представить? Лучший способ, о котором я подумал, - это использовать splay-дерево, ключами которого являются элементы, определяющие эти диапазоны, а значениями - индекс, с которого они начинаются. Затем вы можете за время O(log n) амортизировать выполнить поиск предшественника, чтобы найти предшественника текущего элемента. Это находит самое раннее значение меньше текущего. Затем за время амортизации O(log n) вставьте текущий элемент в дерево. Это представляет собой определение нового диапазона от этого элемента вперед. Чтобы отбросить все диапазоны этого суперседеса, вы затем вырезаете правый дочерний элемент нового узла, который, поскольку это дерево сопряжения находится в корне, из дерева.
В целом, это делает O(n) итераций процесса O(log n) для всего O(n lg n).
Вот алгоритм O(n), использующий DP (фактически O(2n)):
int n = array.length();
Массив min[] записывает минимальное число, найденное от индекса i до конца массива.
int[] min = new int[n];
min[n-1] = array[n-1];
for(int i=n-2; i>=0; i--)
min[i] = Math.min(min[i+1],array[i]);
Ищите и сравнивайте исходный массив и min[].
int[] result = new int[n];
result[n-1] = -1;
for(int i=0; i<n-1; i++)
result[i] = min[i+1]<array[i]?min[i+1]:-1;
Вот новое решение для поиска "следующего меньшего элемента":
int n = array.length();
int[] answer = new int[n];
answer[n-1] = -1;
for(int i=0; i<n-1; i++)
answer[i] = array[i+1]<array[i]?array[i+1]:-1;
All that is actually not required i think
case 1: a,b
answer : -a+b
case 2: a,b,c
answer : a-2b+c
case 3: a,b,c,d
answer : -a+3b-3c+d
case 4 :a,b,c,d,e
answer : a-4b+6c-4d+e
.
.
.
recognize the pattern in it?
it is the pascal's triangle!
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
so it can be calculated using Nth row of pascal's triangle!
with alternate + ans - for odd even levels!
it is O(1)
Решение со сложностью O(n) времени и сложностью O(1) Space. Это решение несложно понять и реализовать без стека.
def min_secMin(a,n):
min = a[0]
sec_min = a[1]
for i in range(1,n):
if(a[i]<min):
sec_min = min
min = a[i]
if(a[i]>min and a[i]<sec_min):
sec_min = a[i]
return min,sec_min
Решение с O(1) пространственной сложностью и O(n) временной сложностью.
void replace_next_smallest(int a[], int n)
{
int ns = a[n - 1];
for (int i = n - 1; i >= 0; i--) {
if (i == n - 1) {
a[i] = -1;
}
else if (a[i] > ns) {
int t = ns;
ns = a[i];
a[i] = t;
}
else if (a[i] == ns) {
a[i] = a[i + 1];
}
else {
ns = a[i];
a[i] = -1;
}
}
}
Учитывая массив, найдите следующий меньший элемент в массиве для каждого элемента, не изменяя исходный порядок элементов. где arr — массив, а n — длина массива. Используя логику Python,
def next_smallest_array(arr,n):
for i in range(0,n-1,1):
if arr[i]>arr[i+1]:
arr[i]=arr[i+1]
else:
arr[i]=-1
arr[n-1]=-1
return arr
- Find_next_smaller_elements([4,2,1,5,3]) Вывод: [2, 1, -1, 3, -1]
- Find_next_smaller_elements([1,2,3,4,5]) Вывод: [-1, -1, -1, -1, -1]