Самый дальний элемент в массиве

Question

В несортированном массиве положительных целых чисел, как найти самый дальний меньший элемент с правой стороны каждого элемента наиболее эффективным способом?

Пример:
Ввод: 6 3 1 82 9 7
Вывод: 2 2 -1 7 -1 7 -1

Объяснение:

Для 6 меньшими элементами на правой стороне являются [3, 1, 2].Поскольку последний наименьший элемент равен 2, он самый дальний из 6. Как и для других.Если такого числа не существует, ответом является «-1»

Answer 1

Одна идея такова:

• Давайте назовем исходный массив A
• , сохраняя массив min [] размера n, из которого min [i] означает минимальное значениеподмассив A [i..n-1].Очевидно, min [i] <= min [i + 1]. </li>
• теперь перемещается справа налево на A. По каждому индексу i выполните бинарный поиск по min [i + 1..n-1.], чтобы найти самое маленькое значение.

Java-код:

    int[] A = { 6, 2, 3, 10, 1, 8 };
    int n = A.length;
    // calculate min
    int[] min = new int[n];
    min[n - 1] = A[n - 1];
    for (int i = n - 2; i >= 0; i--)
        min[i] = Math.min(A[i], min[i + 1]);
    // calculate results
    int[] results = new int[n];
    results[n - 1] = -1;
    for (int i = n - 2; i >= 0; i--) {
        int left = i; // after the binary search, A[left] would be the answer
        int right = n - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (min[mid] < A[i])
                left = mid;
            else
                right = mid - 1;
            if (min[left] < A[i])
                results[i] = min[left];
            else
                results[i] = -1;
        }
    }

Пространственная сложность O (n)

Временная сложность O (nlogn) для всех случаев.

По сравнению с решением из @ vivek_23 приведенный выше алгоритм будет лучше в следующем худшем случае:

Представьте себе случай A из n элементов следующим образом

A= [n / 2 n / 2 .. n / 2 1 2 .. n / 2]

Если мы используем решение стека, предложенное @ vivek_23,

• на шагечтобы найти самый дальний меньший элемент из любого из первых n / 2 элементов (которые все имеют значение n / 2), теперь st1 должен быть равен [1 2 .. n / 2]
• для каждого элемента, имеющего значение n /2, все элементы st1, кроме n / 2, будут перенесены в st2, чтобы найти самый дальний элемент меньшего размера n / 2 - 1. После этого все элементы в st2 будут перенесены обратно в st1.Это приводит к худшей производительности O (n).Поскольку имеется n / 2 элемента, общая наихудшая временная производительность составляет O (n ^ 2).

Answer 2

• Основная идея быстрого получения ответа - использовать стек при перемещении справа налево в массиве.

• Мы вставляем элемент в стек только в одном из следующих двух условий:

  • Если стек пуст.
  • Еслитекущий верхний элемент в стеке больше текущего элемента в итерации.

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

• Итак, вставлять в стек, только если он меньше текущей вершины.

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

Реализация (в java):

    int[] arr = {6,3,1,8,2,9,7};
    Stack<Integer> st1 = new Stack<Integer>();
    Stack<Integer> st2 = new Stack<Integer>();
    List<Integer> result = new ArrayList<>();

    for(int i=arr.length-1;i>=0;--i){
        while(!st1.isEmpty() && arr[(int)st1.peek()] < arr[i]){
            st2.push(st1.pop());
        }

        if(st2.isEmpty()) result.add(-1);
        else result.add(arr[(int)st2.peek()]);

        while(!st2.isEmpty()) st1.push(st2.pop());

        if(st1.isEmpty() || arr[(int)st1.peek()] > arr[i]){
            st1.push(i);
        }
    }

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

Демонстрация: https://ideone.com/0oAasu

Примечание: Вы можете напрямую хранить элементы в стеке вместо индексов, чтобы упростить его.

Обновление: Сложность этого решения действительно равна O (n ^ 2) для случая, когда массив может иметь элементы [ n/2, n/2 ,.. n/2, 1, 2, .. n/2] для массива размером 10 ^ 5 или более.См. Ответ Квинь Тран для лучшего решения.