Алгоритм
.Для вычисления площади данных башен используются два алгоритма: divide и Manhattan_Skyline.
Алгоритм divide выполняет следующие шаги.
1. Принимает два параметра: start и end. Если start равно end, то возвращается список, содержащий два элемента:
[towers [start] [0],towers [start] [2]] и [towers [start] [1],0].
2. В противном случае вычисляется средняя точка между началом и концом и алгоритм рекурсивно вызывается для левой и правой половин списка башен. Затем результаты для левой и правой половин объединяются в новый список.
На этом шаге выполняются следующие действия: • вычисляется средняя позиция;
• создается пустой список merged и инициализируются нулем две переменные i и j;
• инициализируются значением None две переменные h1 и h2;
• в цикле выполняется обход элементов списка merged по диапазону len (left) + len (right);
• если значение i больше или равно длине списка left, то в merged добавляется список, содержащий
[right [j] [0], right [j] [1] if h1 is None else max (h1, right [j] [1])],
затем j увеличивается на 1 и цикл продолжается;
• если значение j больше или равно длине списка right, то в merged добавляется список, содержащий
[left [i] [0], left [i] [1] if h2 is None else max (h2, left [i] [1])],
затем i увеличивается на 1 и цикл продолжается;
• если координата X i-го элемента в left меньше или равна коор- динате X j-го элемента, то в merged добавляется список, содержащий
[left [i] [0], left [i] [1] if h2 is None else max (h2, left[i] [1])],
затем переменной h1 присваивается координата Y i-го элемента в left и i увеличивается на 1;
• в противном случае в merged добавляется список
[right [j] [0], right [j] [1] if h1 is None else max (h1, right [j] [1])],
затем переменной h2 присваивается координата Y j-го элемента в right и j увеличивается на 1.
3. В завершение возвращается объединенный список merged.
Алгоритм Manhattan_Skyline выполняет следующие шаги.
1. Принимает список башен towers.
2. Вычисляет площадь, ограниченную линией горизонта, с использованием divide.
3. Возвращает вычисленную площадь.