题目描述

矩形蛋糕的高度为 h 且宽度为 w，给定两个整数数组 horizontalCuts 和 verticalCuts，其中 horizontalCuts[i] 是从矩形蛋糕顶部到第 i 个水平切口的距离，类似地，verticalCuts[j] 是从矩形蛋糕的左侧到第 j 个竖直切口的距离。

请你按数组 horizontalCuts 和 verticalCuts 中提供的水平和竖直位置切割后，请你找出 面积最大 的那份蛋糕，并返回其 面积。由于答案可能是一个很大的数字，因此需要将结果对 10^9 + 7 取余后返回。

样例

输入：h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]
输出：4 
解释：上图所示的矩阵蛋糕中，红色线表示水平和竖直方向上的切口。
切割蛋糕后，绿色的那份蛋糕面积最大。

输入：h = 5, w = 4, horizontalCuts = [3,1], verticalCuts = [1]
输出：6
解释：上图所示的矩阵蛋糕中，红色线表示水平和竖直方向上的切口。
切割蛋糕后，绿色和黄色的两份蛋糕面积最大。

输入：h = 5, w = 4, horizontalCuts = [3], verticalCuts = [3]
输出：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 中的所有元素各不相同。

算法

(贪心) $O(r \log r + c \log c)$

1. 将水平和竖直数组分别排序，然后分别找最大间隔。
2. 最大间隔的乘积就是答案。

时间复杂度

• 排序的时间复杂度为 $O(r \log r + c \log c)$。
• 找最大间隔的时间复杂度为 $O(r + c)$，故总时间复杂度为 $O(r \log r + c \log c)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int maxArea(int h, int w,
                vector<int>& horizontalCuts, vector<int>& verticalCuts) {
        #define LL long long
        const int mod = 1000000007;

        sort(horizontalCuts.begin(), horizontalCuts.end());
        sort(verticalCuts.begin(), verticalCuts.end());

        int r = horizontalCuts.size(), c = verticalCuts.size();

        int mar = max(horizontalCuts[0], h - horizontalCuts.back());

        for (int i = 1; i < r; i++)
            mar = max(mar, horizontalCuts[i] - horizontalCuts[i - 1]);

        int mac = max(verticalCuts[0], w - verticalCuts.back());

        for (int i = 1; i < c; i++)
            mac = max(mac, verticalCuts[i] - verticalCuts[i - 1]);

        return (LL)(mar) * mac % mod;
    }
};