Высота башни из падающих фигур в двух колонках

Условие

В учебном поле две колонки, клетки не удаляются. Фигура 1 — вертикальная полоса из 3 клеток в левой колонке; 2 — горизонтальная полоса из 2 клеток, по одной в каждой; 3 — вертикальная полоса из 3 клеток справа. Фигуры падают вниз, не двигаются вбок и не вращаются. Найдите высоту башни.

Ответ

Достаточно хранить высоты двух колонок. Вертикальная фигура увеличивает свою высоту на 3, горизонтальная устанавливает обе высоты в max(left, right) + 1.

Решение:

function findHeight(figures) {
  let left = 0, right = 0;
  for (const figure of figures) {
    if (figure === 1) left += 3;
    else if (figure === 3) right += 3;
    else if (figure === 2) left = right = Math.max(left, right) + 1;
    else throw new Error('Unknown figure');
  }
  return Math.max(left, right);
}

Получаем 7 для [1,2,3], 12 для [1,1,1,1] и 0 для пустого массива. Время O(n), память O(1).