Максимальная площадь пирога после горизонтального и вертикального разрезов

Даны два положительных целых числа h и w , представляющие высоту h и ширину w , которые образуют прямоугольник. Кроме того, есть два массива целых чисел: horizontalCuts и verticalCuts , где horizontalCuts[i] — расстояние от вершины прямоугольника до i -го горизонтального разреза и, аналогично, verticalCuts[j] — расстояние от левого края прямоугольника до j -го вертикального разреза. . Задача состоит в том, чтобы найти максимальную площадь прямоугольника после того, как вы вырезаете в каждой позиции по горизонтали и вертикали, представленной в массивах horizontalCuts и verticalCuts . Поскольку ответ может быть огромным числом, верните это значение по модулю 10^9 + 7.

Примеры :

Input: h = 6, w = 4, horizontalCuts = [2, 5], verticalCuts = [1, 3]
Output: 6
Explanation: The figure above represents the given rectangle. Red lines are the horizontal cuts and blue lines are vertical cuts. After the rectangle is cut, the green piece of rectangle has the maximum area.

Input: h = 5, w = 4, horizontalCuts = [3, 1], verticalCuts = [1]
Output: 9
 

Подход: проблему можно решить, заметив, что:

• Если HorizonCuts перпендикулярны любому VerticalCut, то все вертикальные срезы пересекают все HorizonCuts.
• Затем максимальная площадь прямоугольника должна быть ограничена хотя бы одним вертикальным и одним горизонтальным разрезом.

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

• Сортировка массива horizontalCuts и verticalCuts .
• Инициализируйте две переменные, скажем MaxHorizontal и MaxVertical , как horizontalCuts[0] и verticalCuts[0] соответственно, чтобы рассматривать ближайшие прямоугольники к оси как по горизонтали, так и по вертикали, которые будут хранить максимальную горизонтальную и вертикальную длину прямоугольника соответственно.
• Выполните итерацию в диапазоне [1, horizontalCuts.size()-1] , используя переменную i , и выполните следующие шаги:
  • Измените значение MaxHorizontal на max(MaxHorizontal, horizontalCuts[i] – horizontalCuts[i-1]) .
  • Измените значение MaxVertical на max(MaxVertical, verticalCuts[i] – verticalCuts[i-1]) .
• В качестве ответа выведите MaxHorizontal*MaxVertical .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(NlogN)
Вспомогательное пространство: O(1)