Учитывая массив, узнайте следующий меньший элемент для каждого элемента

Ответ 1

O (N) Алгоритм

• Инициализировать выходной массив для всех -1s.
• Создайте пустой стек индексов элементов, которые мы посетили во входном массиве, но еще не знаем ответа в выходном массиве.
• Итерации по каждому элементу входного массива:
  • Чем меньше элемент, индексированный вершиной стека?
    • Да. Это первый такой элемент. Заполните соответствующий элемент в нашем выходном массиве, удалите элемент из стека и повторите попытку, пока стек не будет пуст или ответ будет отсутствовать.
    • Нет. Продолжайте 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, чтобы инициализировать его до -1s при его создании.

Сложность времени

Это O (N). Основной цикл явно посещает каждый индекс один раз. Каждый индекс добавляется в стек ровно один раз и удаляется не более одного раза.

Решение как вопрос интервью

Этот вопрос может быть довольно пугающим в интервью, но я хотел бы отметить, что (надеюсь) интервьюер не ожидает, что решение spring полностью сформировано из вашего ума. Расскажите им о своем процессе мышления. Мой сделал что-то вроде этого:

• Есть ли какая-то связь между позициями чисел и их следующим меньшим числом в массиве? Знает ли кто-то из них ограничение того, что могут быть другие?
• Если бы я был перед доской, я бы, вероятно, набросал массив примеров и рисовал линии между элементами. Я мог бы также нарисовать их как 2D-гистограмму - горизонтальная ось - это позиция в входном массиве, а вертикальная ось - значение.
• У меня была догадка, что это покажет образец, но не бумагу. Я думаю, что диаграмма сделает это очевидным. Думая об этом осторожно, я мог видеть, что линии не будут перекрываться произвольно, но будут только гнездиться.
• Вокруг этого момента мне пришло в голову, что это невероятно похоже на алгоритм, используемый Python внутри, чтобы преобразовать отступы в виртуальные токены INDENT и DEDENT, о которых я читал раньше. См. "Как компилятор разбирает отступы?" на этой странице: http://www.secnetix.de/olli/Python/block_indentation.hawk Однако, только когда я на самом деле разработал алгоритм, за которым я следил за этой мыслью и решил, что это на самом деле то же самое, поэтому я не думаю, что это слишком помогло. Тем не менее, если вы видите сходство с какой-либо другой проблемой, которую вы знаете, вероятно, стоит упомянуть об этом и сказать, как она похожа и как она отличается.
• Теперь появилась общая форма алгоритма на основе стека, но мне все же нужно было подумать об этом немного больше, чтобы быть уверенным, что это будет хорошо работать для тех элементов, у которых нет последующего меньшего элемента.

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

Ответ 2

Начните создавать BST, начиная с конца массива. Для каждого значения "v" ответ был бы последним node "Правильно", который вы взяли на пути к вставке "v", о котором вы можете легко отслеживать в рекурсивной или итеративной версии. ОБНОВЛЕНИЕ:

Следуя вашим требованиям, вы можете приблизиться к этому линейным образом:

Если каждый следующий элемент меньше текущего элемента (например, 6 5 4 3 2 1), вы можете обрабатывать это линейно, не требуя дополнительной памяти. Интересный случай возникает, когда вы начинаете получать запутанные элементы (например, 4 2 1 5 3), и в этом случае вам нужно запомнить их порядок, пока вы не получаете их "меньшие копии". Простой подход на основе стека выглядит следующим образом:

Нажмите первый элемент (a [0]) в стеке.

Для каждого следующего элемента a [i] вы заглядываете в стек и если значение (peek()) больше, чем тот, что находится в руке a [i], вы получили следующее меньшее меньшее число для этого элемента стека (peek ( )) {и продолжайте выскакивать элементы до тех пор, пока peek() > a [i]}. Выполните их и распечатайте/сохраните соответствующее значение. иначе просто отбросьте свой [i] в ​​стек.

В конце стека ll содержат те элементы, у которых никогда не было значения меньше их (справа). Вы можете заполнить -1 для них в своем объеме.

например. A = [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.

Ответ 3

Предполагая, что вы имели в виду первый следующий элемент, который ниже текущего элемента, вот 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.

Ответ 4

По некоторым причинам мне легче рассуждать о "предыдущем меньшем элементе", aka "все ближайшие более мелкие элементы" . Таким образом, примененное назад дает "следующее меньшее".

Для записи реализация 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]

Ответ 5

Вот код javascript. Этот видео объясняет Algo лучше

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]

Ответ 6

Вот замечание, которое, я думаю, можно сделать в решении O (n log n). Предположим, у вас есть ответ для последних k элементов массива. Что вам нужно, чтобы выяснить значение элемента перед этим? Вы можете думать о том, что последние k-элементы разделены на ряд диапазонов, каждый из которых начинается с какого-то элемента и продолжается до тех пор, пока не ударит меньший элемент. Эти диапазоны должны быть в порядке убывания, поэтому вы можете подумать о том, чтобы выполнить двоичный поиск по ним, чтобы найти первый интервал, меньший, чем этот элемент. Затем вы можете обновить диапазоны, чтобы учитывать этот новый элемент.

Теперь, как лучше всего это представить? Лучший способ, который я думал, - использовать дерево splay, ключи которого являются элементами, определяющими эти диапазоны, и значениями которых является индекс, с которого они начинаются. Затем вы можете в течение времени O (log n) амортизировать выполнить предшествующий поиск, чтобы найти предшественника текущего элемента. Это находит самое раннее значение меньше текущего. Затем, в амортизированном времени O (log n), вставьте текущий элемент в дерево. Это означает определение нового диапазона из этого элемента вперед. Чтобы отбросить все диапазоны, это отменяет, затем вырезаете правый дочерний элемент нового node, который, поскольку это дерево воспроизведения находится в корне, из дерева.

В целом, это O (n) итерации процесса O (log n) для полного O (n lg n).

Ответ 7

Вот алгоритм 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]);

Найдите и сравните исходный массив и мин [].

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;

Ответ 8

        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 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 triangle!
    with alternate + ans - for odd even levels!
    it is O(1)

Ответ 9

Вы можете решить эту проблему во время выполнения O (n) с помощью сложности O (n). Начните с Stack и продолжайте нажимать элементы до тех пор, пока не найдете arr [i], для которых элемент arr [i] <stack.top. Затем сохраните этот индекс.

Фрагмент кода:

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;
}

Ответ 10

Решение с комплексной сложностью 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;                                                                              
            }                                                                                           
        }                                                                                               
    }