1465. Max Area After Horizontal and Vertical Cuts

Question

You are given a rectangular cake of size h x w and two arrays of integers horizontalCuts and verticalCuts where:

• horizontalCuts[i] is the distance from the top of the rectangular cake to the i<sup>th</sup> horizontal cut and similarly, and
• verticalCuts[j] is the distance from the left of the rectangular cake to the j<sup>th</sup> vertical cut.

Return the maximum area of a piece of cake after you cut at each horizontal and vertical position provided in the arrays horizontalCuts and verticalCuts. Since the answer can be a large number, return this modulo 10<sup>9</sup><span> </span>+ 7.

Solution

先排序，记录两次切割之间的距离的最大值。
最后同样需要比较蛋糕的总尺寸和最后一次切割的距离。

返回宽度和长度的最大值的乘积即可。

注意：两个int整数相乘会溢出，max需要记录为long类型。

Code

class Solution {
    public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
        int MOD = (int) Math.pow(10,9)+7;
        Arrays.sort(horizontalCuts);
        Arrays.sort(verticalCuts);
        long maxH = 0, maxV = 0;
        int lastH = 0, lastV = 0;
        
        for(int i = 0; i < horizontalCuts.length; i++){
            maxH = Math.max(maxH, horizontalCuts[i] - lastH);
            lastH = horizontalCuts[i];
        }
        
        maxH = Math.max(maxH, h - lastH);
        
        for(int i = 0; i < verticalCuts.length; i++){
            maxV = Math.max(maxV, verticalCuts[i] - lastV);
            lastV = verticalCuts[i];
        }
        
        maxV = Math.max(maxV, w - lastV);
        return (int) (maxV * maxH % MOD) ;
    }
}