← Static tasks

1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts

leetcode medium

#array#csharp#leetcode#math#medium#sort

Task

Дан прямоугольный торт размером 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.

C# solution

matched/original
public class Solution {
    public int MaxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
        Array.Sort(horizontalCuts);
        Array.Sort(verticalCuts);
        
        long maxHeight = Math.Max(horizontalCuts[0], h - horizontalCuts[^1]);
        for (int i = 1; i < horizontalCuts.Length; i++) {
            maxHeight = Math.Max(maxHeight, horizontalCuts[i] - horizontalCuts[i - 1]);
        }
        
        long maxWidth = Math.Max(verticalCuts[0], w - verticalCuts[^1]);
        for (int i = 1; i < verticalCuts.Length; i++) {
            maxWidth = Math.Max(maxWidth, verticalCuts[i] - verticalCuts[i - 1]);
        }
        
        return (int)((maxHeight * maxWidth) % 1000000007);
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MaxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {
        sort(horizontalCuts.begin(), horizontalCuts.end());
        sort(verticalCuts.begin(), verticalCuts.end());
        
        long maxHeight = max(horizontalCuts[0], h - horizontalCuts[^1]);
        for (int i = 1; i < horizontalCuts.size(); i++) {
            maxHeight = max(maxHeight, horizontalCuts[i] - horizontalCuts[i - 1]);
        }
        
        long maxWidth = max(verticalCuts[0], w - verticalCuts[^1]);
        for (int i = 1; i < verticalCuts.size(); i++) {
            maxWidth = max(maxWidth, verticalCuts[i] - verticalCuts[i - 1]);
        }
        
        return (int)((maxHeight * maxWidth) % 1000000007);
    }
}

Java solution

matched/original
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));
    }
}

Go solution

matched/original
func maxArea(h int, w int, horizontalCuts []int, verticalCuts []int) int {
    sort.Ints(horizontalCuts)
    sort.Ints(verticalCuts)
    
    maxHeight := max(horizontalCuts[0], h - horizontalCuts[len(horizontalCuts)-1])
    for i := 1; i < len(horizontalCuts); i++ {
        maxHeight = max(maxHeight, horizontalCuts[i] - horizontalCuts[i-1])
    }
    
    maxWidth := max(verticalCuts[0], w - verticalCuts[len(verticalCuts)-1])
    for i := 1; i < len(verticalCuts); i++ {
        maxWidth = max(maxWidth, verticalCuts[i] - verticalCuts[i-1])
    }
    
    return (maxHeight * maxWidth) % 1000000007
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Explanation

Algorithm

Отсортируйте массивы horizontalCuts и verticalCuts в порядке возрастания. Найдите максимальную высоту, учитывая верхний и нижний края торта, и пройдитесь по массиву horizontalCuts, чтобы найти максимальное расстояние между соседними разрезами.

Найдите максимальную ширину, учитывая левый и правый края торта, и пройдитесь по массиву verticalCuts, чтобы найти максимальное расстояние между соседними разрезами.

Верните произведение максимальной высоты и максимальной ширины, взятое по модулю 10^9+7.

😎