Быстрое решение для Leetcode 1465



Максимальная площадь торта после горизонтального и вертикального разрезов (Leetcode 1465) —
дан прямоугольный торт высотой h и шириной w и два массива целых чисел horizontalCuts и вертикальные разрезы, где…theswiftnerd.com



Вы можете прочитать полную историю в блоге The Swift Nerd по ссылке выше.

Постановка задачи

Дан прямоугольный торт высотой h и шириной w, а также два массива целых чисел horizontalCuts и verticalCuts, где horizontalCuts[i] — расстояние от верха прямоугольного торта до горизонтального разреза ith и, аналогично, verticalCuts[j] — расстояние слева от прямоугольного торта. до вертикального разреза jth.

Возвращает максимальную площадь куска пирога после разрезания в каждой позиции по горизонтали и вертикали, заданной в массивах horizontalCuts и verticalCuts. Поскольку ответ может быть огромным числом, верните его по модулю 10^9 + 7.

Примеры

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

Input: h = 5, w = 4, horizontalCuts = [3,1], verticalCuts = [1]
Output: 6
Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts. After you cut the cake, the green and yellow pieces of cake have the maximum area.
Input: h = 5, w = 4, horizontalCuts = [3], verticalCuts = [3]
Output: 9

Ограничения

  • 2 <= h, w <= 10^9
  • 1 <= horizontalCuts.length < min(h, 10^5)
  • 1 <= verticalCuts.length < min(w, 10^5)
  • 1 <= horizontalCuts[i] < h
  • 1 <= verticalCuts[i] < w
  • Гарантируется, что все элементы в horizontalCuts различны.
  • Гарантируется, что все элементы в verticalCuts различны.

Интуиция

Мы пытаемся найти все возможные прямоугольники и найти прямоугольник с максимальной площадью, но это было бы очень дорого для больших значений h, w. Если мы подумаем о максимизации площади, мы увидим, что проблема действительно проста, и нам нужно найти максимальные промежутки между горизонтальными и вертикальными линиями, чтобы сформировать нашу площадь.

Суть проблемы заключается в том, что не все разрезы (горизонтальные или вертикальные) имеют значение. Если мы думаем о площади, то это ширина * высота, и чтобы площадь была максимальной, ширина и высота должны быть максимальными. При итерации, скажем, на горизонтальных разрезах расстояние между двумя соседними разрезами будет составлять прямоугольник с высотой horizontalCuts[i]- horizontalCuts[i-1]. Мы можем найти все промежутки и сохранить максимальное значение (maxHeight). Точно так же повторение вертикальных разрезов поможет нам найти maxWidth.

Также имейте в виду крайний случай для рассмотрения значений границ для ширины и высоты. Начальная ширина будет составлять от 0 до verticalCuts[0], а крайняя последняя ширина будет равна w — verticalCuts[n-1]. Точно так же для начальной и последней высоты, которые мы можем определить, инициализируя maxHeight = max(horizontalCuts[0], w — horizontalCuts[n-1]) и maxWidth = max(verticalCuts[0 ], h — вертикальные разрезы[n-1]).

Анализ сложности

Мы сортируем наши горизонтальные и вертикальные разрезы, что является операцией O(NLogN). Если рассматривать M как длину горизонтальных разрезов, а N как длину вертикальных разрезов, то общая сложность будет ограничена O(MLogM) + O(NLogN).

Время = O(MLogM) + O(NLogN)

Пробел = O(1)

Спасибо за чтение. Если вам понравилась эта статья и вы сочли ее полезной, делитесь ею и распространяйте как лесной пожар!

Вы можете найти меня на TheSwiftNerd | ЛинкедИн | Гитхаб