Medium
题目描述
给你一个矩形蛋糕，尺寸为 h x w，以及两个整数数组 horizontalCuts 和 verticalCuts，其中：
- horizontalCuts[i] 是从矩形蛋糕顶部到第 i 个水平切口的距离
- verticalCuts[j] 是从矩形蛋糕左侧到第 j 个竖直切口的距离
请你按照数组 horizontalCuts 和 verticalCuts 中给出的水平和竖直位置切割后，请你找出面积最大的那块蛋糕，并返回其面积。由于答案可能是一个很大的数字，因此需要将结果对 10^9 + 7 取余后返回。
示例 1：
输入：h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]
输出：4
解释：上图表示了给定的矩形蛋糕。红线表示水平和竖直方向上的切割线。切割蛋糕后，绿色的那块蛋糕具有最大的面积。
示例 2：
输入：h = 5, w = 4, horizontalCuts = [3,1], verticalCuts = [1]
输出：6
解释：上图表示了给定的矩形蛋糕。红线表示水平和竖直方向上的切割线。切割蛋糕后，绿色和黄色的那两块蛋糕具有最大的面积。
示例 3：
输入：h = 5, w = 4, horizontalCuts = [3], verticalCuts = [3]
输出：9
约束条件：
- 2 <= h, w <= 10^9
- 1 <= horizontalCuts.length <= min(h - 1, 10^5)
- 1 <= verticalCuts.length <= min(w - 1, 10^5)
- 1 <= horizontalCuts[i] < h
- 1 <= verticalCuts[i] < w
- horizontalCuts 中的所有元素都是不同的
- verticalCuts 中的所有元素都是不同的
解题思路
这道题的核心思路是：蛋糕被切割后，最大的矩形块面积等于最大水平间距与最大竖直间距的乘积。
解题步骤如下：
排序切割位置：将水平切割和竖直切割数组分别排序，便于计算相邻切割线之间的距离。
添加边界：为了计算边界到第一个切割线和最后一个切割线到边界的距离，需要在数组开头添加 0，结尾添加蛋糕的高度/宽度。
计算最大间距：
- 遍历排序后的水平切割数组，计算相邻两个位置之间的最大距离
- 遍历排序后的竖直切割数组，计算相邻两个位置之间的最大距离
计算结果：最大面积 = 最大水平间距 × 最大竖直间距，最后对 10^9 + 7 取余。
时间复杂度主要来自排序操作，空间复杂度为常数级别（不考虑排序的额外空间）。这是一个典型的贪心算法应用，通过找到局部最优解（最大间距）来获得全局最优解。
代码实现
class Solution {
public:
int maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {
const int MOD = 1e9 + 7;
// 排序并添加边界
horizontalCuts.push_back(0);
horizontalCuts.push_back(h);
verticalCuts.push_back(0);
verticalCuts.push_back(w);
sort(horizontalCuts.begin(), horizontalCuts.end());
sort(verticalCuts.begin(), verticalCuts.end());
// 计算最大水平间距
int maxH = 0;
for (int i = 1; i < horizontalCuts.size(); i++) {
maxH = max(maxH, horizontalCuts[i] - horizontalCuts[i-1]);
}
// 计算最大竖直间距
int maxW = 0;
for (int i = 1; i < verticalCuts.size(); i++) {
maxW = max(maxW, verticalCuts[i] - verticalCuts[i-1]);
}
return (1LL * maxH * maxW) % MOD;
}
};
class Solution:
def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
MOD = 10**9 + 7
# 排序并添加边界
horizontalCuts.extend([0, h])
verticalCuts.extend([0, w])
horizontalCuts.sort()
verticalCuts.sort()
# 计算最大水平间距
max_h = 0
for i in range(1, len(horizontalCuts)):
max_h = max(max_h, horizontalCuts[i] - horizontalCuts[i-1])
# 计算最大竖直间距
max_w = 0
for i in range(1, len(verticalCuts)):
max_w = max(max_w, verticalCuts[i] - verticalCuts[i-1])
return (max_h * max_w) % MOD
public class Solution {
public int MaxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
const int MOD = 1000000007;
// 添加边界并排序
var hCuts = new List<int>(horizontalCuts) { 0, h };
var vCuts = new List<int>(verticalCuts) { 0, w };
hCuts.Sort();
vCuts.Sort();
// 计算最大水平间距
int maxH = 0;
for (int i = 1; i < hCuts.Count; i++) {
maxH = Math.Max(maxH, hCuts[i] - hCuts[i-1]);
}
// 计算最大竖直间距
int maxW = 0;
for (int i = 1; i < vCuts.Count; i++) {
maxW = Math.Max(maxW, vCuts[i] - vCuts[i-1]);
}
return (int)((long)maxH * maxW % MOD);
}
}
var maxArea = function(h, w, horizontalCuts, verticalCuts) {
const MOD = 1e9 + 7;
// 排序并添加边界
horizontalCuts.push(0, h);
verticalCuts.push(0, w);
horizontalCuts.sort((a, b) => a - b);
verticalCuts.sort((a, b) => a - b);
// 计算最大水平间距
let maxH = 0;
for (let i = 1; i < horizontalCuts.length; i++) {
maxH = Math.max(maxH, horizontalCuts[i] - horizontalCuts[i-1]);
}
// 计算最大竖直间距
let maxW = 0;
for (let i = 1; i < verticalCuts.length; i++) {
maxW = Math.max(maxW, verticalCuts[i] - verticalCuts[i-1]);
}
return (maxH * maxW) % MOD;
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(m log m + n log n) | m 为水平切割数量，n 为竖直切割数量，主要时间消耗在排序上 |
| 空间复杂度 | O(1) | 只使用常数级额外空间（不考虑排序的额外空间） |