Сложность: medium
Дан прямоугольный торт размером h x w и два массива целых чисел horizontalCuts и verticalCuts, где:
horizontalCuts[i] — это расстояние от верхнего края прямоугольного торта до i-го горизонтального разреза,
verticalCuts[j] — это расстояние от левого края прямоугольного торта до j-го вертикального разреза.
Верните максимальную площадь кусочка торта после разрезания в каждом горизонтальном и вертикальном положении, указанном в массивах 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.
👨💻 Алгоритм:
1⃣Отсортируйте массивы horizontalCuts и verticalCuts в порядке возрастания. Найдите максимальную высоту, учитывая верхний и нижний края торта, и пройдитесь по массиву horizontalCuts, чтобы найти максимальное расстояние между соседними разрезами.
2⃣Найдите максимальную ширину, учитывая левый и правый края торта, и пройдитесь по массиву verticalCuts, чтобы найти максимальное расстояние между соседними разрезами.
3⃣Верните произведение максимальной высоты и максимальной ширины, взятое по модулю 10^9+7.
😎 Решение:
class Solution {
public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
Arrays.sort(horizontalCuts);
Arrays.sort(verticalCuts);
int n = horizontalCuts.length;
int m = verticalCuts.length;
long maxHeight = Math.max(horizontalCuts[0], h - horizontalCuts[n - 1]);
for (int i = 1; i < n; i++) {
maxHeight = Math.max(maxHeight, horizontalCuts[i] - horizontalCuts[i - 1]);
}
long maxWidth = Math.max(verticalCuts[0], w - verticalCuts[m - 1]);
for (int i = 1; i < m; i++){
maxWidth = Math.max(maxWidth, verticalCuts[i] - verticalCuts[i - 1]);
}
return (int) ((maxWidth * maxHeight) % (1000000007));
}
}Ставь 👍 и забирай 📚 Базу знаний