原题链接:
https://leetcode.cn/problems/maximum-area-of-a-piece-of-cake-after-horizontal-and-vertical-cuts/

解法1: 贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    /** 
        贪心
        因为窗口都是由两条横切 和 两条纵切直接确定
        所以先确定横切 然后求出纵切最大那么最后得到的就是答案
    */
    public final int MOD = (int)(1e9 + 7);
    // 他这里面 horizontalCuts verticalCuts 里面给都不是排序好的 还是有些坑的
    public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
        return (int)((getMax(horizontalCuts,h) * getMax(verticalCuts,w)) % MOD);
    }
    
    public static long getMax(int [] arr ,int x){
        int n = arr.length;
        Arrays.sort(arr);
        int res =  Math.max(arr[0],x - arr[n - 1]);

        for(int i = 1; i < n ; i++ ){
            res = Math.max(arr[i] - arr[i - 1],res);
        }

        return (long)res;
    }

}