Алгоритм линейного времени для нарезки уложенных ящиков

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

Вот проблема:

Вам представлена ​​стена с колоннами разной высоты. Каждая высота столбца представлена ​​в виде ненулевых целых чисел.

Состояние ввода определяется с помощью массива H длины N, содержащего высоты каждого столбцов N на экране, например:

Tetris snapshot defined using the <code>H</code> array

Нарезка моментального снимка на заданной высоте оставляет несколько твердых фигур выше эта высота. Например. срезание на уровне 2 разрезало бы 3 сплошные части:

Slicing at level 2

Нарезка на уровне 1 также разрежет 3 сплошные части:

Slicing at level 1

Аналогично, нарезка на уровне 0 вернет единую (одну) сплошную фигуру, а срезание на уровне 3 не будет вырезать какие-либо фигуры.

Требование:. Учитывая массив высот срезов S длины M, содержащий все Уровни, на которых должен выполняться "срез", возвращают массив длиной M, содержащий числа разрезанных кусков для каждого соответствующего разреза.

Например, учитывая ввод H = {2, 1, 3, 2, 3, 1, 1, 2} и S = { 0, 1, 2, 3 }, программа должна возвращать величины {1, 3, 3, 0}, согласно приведенным выше примерам.

Оба N и M находятся в диапазоне около 20,000, но высоты в каждом массиве могут достигать 1,000,000.

И время и пространство в худшем случае сложность решения не может превышать O(N + M + max(M) + max(N)).

Последнее ограничение - это то, что меня озадачивает: это в основном означает, что я не могу иметь вложенные for -loops, и я не могу избежать этого.

Очевидно, что существует некоторая умная препроцессия, которая должна быть выполнена для получения конечных результатов в O(1) за один срез, но я не смог его найти.

Я продолжал создавать массив сокращенных номеров для каждого уровня среза, а затем обновлял их все, как итерацию через H, но это оказывается O(N*M), так как мне нужно обновить всю нижнюю высоту уровни.

Существует ли структура данных, подходящая для этой задачи?

Ответы

Ответ 1

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

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

Таким образом, мы можем вычислить количество частей таким образом:

  • Создайте массив Accumulator размера max(S), заполненный нулями.
  • Итерации над H, и для каждого вертикального края, с которым вы сталкиваетесь, добавьте +1 в индекс i в Accumulator, соответствующий высоте нижнего конца края, и добавьте -1 в индекс j в соответствии с верхним краем края. Мы считаем "уровень земли" равным нулю. Не забудьте включить передний и задний края!
  • Итерации над Accumulator и вставьте в каждую ячейку сумму всех ячеек до и включите ее (O(max(S)) время, если вы сохраните текущую сумму)
  • Разделите каждое значение в Accumulator на 2, чтобы получить количество штук на каждой высоте.
  • Считать количество штук, соответствующих высотам в S.

Пример:

Конечными точками края слева направо являются

0,2
1,2
1,3
2,3
2,3
1,3
1,3
0,3

Итак, наш массив Accumulator выглядит следующим образом:

{2, 4, 0, -6}

Что после этапа накопления выглядит следующим образом:

{2, 6, 6, 0}

Это означает, что количество деталей

{1, 3, 3, 0}

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

Ответ 2

Step 1: Maintain 3 column list (height, index_start, index_end)
Step 2: Sort the list according to height as primary key (decreasing), index_start as secondary key
Step 3: Let h be the highest height
Step 4: Merge all columns at height at least h and contiguous block
Step 5: Resulting number of blocks is blocks at height h
Step 6: h=h-1
Step 7: Go to step 4

Это грубый алго. Эффективно сложность O (nlogn)