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

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

Пример реализации на Java:

public static int[] solve(int[] input) {
    int[] output = new int[input.length], stk = new int[input.length];
    int top = -1;
    for (int i = input.length - 1; i >= 0; i--) {
        int low = 0, high = top;
        while (low <= high) {
            int mid = low + high >>> 1;
            if (stk[mid] < 2 * input[i]) high = mid - 1;
            else low = mid + 1;
        }
        output[i] = high < 0 ? -1 : stk[high];
        while (top >= 0 && input[i] >= stk[top]) --top;
        stk[++top] = input[i];
    }
    return output;
}

Вот решение, которое O(n log n) использует минимальную кучу (реализованную с помощью библиотеки heapq в Python) кортежей (value, index). Он работает, перебирая массив, сравнивая текущее значение с наименьшим значением в куче и проверяя, больше ли оно в два раза. Пока это так, соответствующий индекс в выходных данных устанавливается на это значение. Текущее значение затем помещается в кучу.

from heapq import heappop, heappush

def two_x(arr):
    heap = []
    out = [-1] * len(arr)
    for i, v in enumerate(arr):
        while heap and v >= 2 * heap[0][0]:
            out[heappop(heap)[1]] = v
        heappush(heap, (v, i))
    return out

two_x([23, 35, 12, 47, 33, 68, 34])

Выход:

[47, -1, 47, -1, 68, -1, -1]

Другое решение O(nlog(n)) — пройти по массиву, сохраняя при этом индексы прошлых элементов, которые все еще ожидают своей второй половинки.

Решение находится на Ruby.

Вспомогательный метод

Сначала вспомогательный метод, который будет вставлять n в массив unmatched, сохраняя массив отсортированным.

def insert_in_unmatched(unmatched, n)
  i = unmatched.bsearch_index { |m| m > n }
  unmatched.insert(i, n)
end

Методы Array#bsearch_index и Array#insert оба написаны на C, поэтому они должны быть достаточно эффективными.

Например,

unmatched = [1, 2, 2, 5, 7, Float::INFINITY]
insert_in_unmatched(unmatched, 3)
unmatched
  #=> [1, 2, 2, 3, 5, 7, Infinity]

unmatched = [1, 2, 2, 5, 7, Float::INFINITY]
insert_in_unmatched(unmatched, 0)
unmatched
  #=> [1, 2, 2, 3, 5, 7, Infinity]

unmatched = [1, 2, 2, 5, 7, Float::INFINITY]
insert_in_unmatched(unmatched, 8)
unmatched
  #=> [1, 2, 2, 5, 7, 8, Infinity]

Основной метод

Основной метод следующий.

def doit(arr)
  output = Array.new(arr.size)
  unmatched = [Float::INFINITY]
  unmatched_to_index = Hash.new { |h,k| h[k] = [] }
  arr.each_with_index do |n,i|
    loop do
      break if unmatched.empty?
      m = unmatched.first
      break if 2*m > n
      unmatched_to_index[m].each { |k| output[k] = n }
      unmatched_to_index.delete(m)
      unmatched.shift
    end
    insert_in_unmatched(unmatched, n)
    unmatched_to_index[n] << i     
  end
  output
end

Примечания

• output = Array.new(arr.size) использует метод Array::new для создания массива, содержащего столько же элементов, сколько и массив arr, причем эти элементы изначально равны nil.

• unmatched_to_index = Hash.new { |h,k| h[k] = [] } использует одну из форм метода Hash::new для создания хеша, обладающего свойством: если h не имеет ключа k, h[k] сначала устанавливает значение k, равное пустому массиву. Например, если

  ч = { 2=>[0], 4=>[2,3] }

тогда h[3] << 1 приводит к

h #=> { 2=>[0], 4=>[2,3], 3=>[1] }

Значение 3 изначально устанавливается в пустой массив, [] затем << 1 добавляет 1 к этому массиву.

Если бы за этим следовал h[3] << 4, 4 просто был бы добавлен к существующему массиву [1]:

h #=> { 2=>[0], 4=>[2,3], 3=>[1,4] }

• Когда рассматривается элемент n с индексом i из arr, unmatched представляет собой отсортированный массив элементов arr[j], j < i, которые еще не сопоставлены с первым элементом arr[k], k > j, для которого 2*arr[j] <= arr[k].

• break if unmatched.empty? просто выходит из бесконечного цикла loop, если unmatched пусто.

• Для каждого k массива unmatched_to_index[m], arr[k] #=> m.

• unmatched_to_index[m].each { |k| output[k] = n } назначает arr[i] #=> n первым элементом в arr, для которого 2*m <= n, где m — значение всех элементов k в unmatched_to_index[m], для которых arr[k] #=> m и k < i.

• unmatched.shift удаляет первый элемент unmatched.