LeetCode 题解工作台
切割后面积最大的蛋糕
矩形蛋糕的高度为 h 且宽度为 w ，给你两个整数数组 horizontalCuts 和 verticalCuts ，其中： horizontalCuts[i] 是从矩形蛋糕顶部到第 i 个水平切口的距离 verticalCuts[j] 是从矩形蛋糕的左侧到第 j 个竖直切口的距离 请你按数组 ho…
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
我们先分别对 `horizontalCuts` 和 `verticalCuts` 排序，然后分别遍历两个数组，计算相邻两个元素的最大差值，分别记为 和 ，最后返回 $x \times y$ 即可。 注意要考虑边界情况，即 `horizontalCuts` 和 `verticalCuts` 的首尾元素。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
矩形蛋糕的高度为 h 且宽度为 w，给你两个整数数组 horizontalCuts 和 verticalCuts，其中：
-
horizontalCuts[i]是从矩形蛋糕顶部到第i个水平切口的距离 verticalCuts[j]是从矩形蛋糕的左侧到第j个竖直切口的距离
请你按数组 horizontalCuts 和 verticalCuts 中提供的水平和竖直位置切割后，请你找出 面积最大 的那份蛋糕，并返回其 面积 。由于答案可能是一个很大的数字，因此需要将结果 对 109 + 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 <= 1091 <= horizontalCuts.length <= min(h - 1, 105)1 <= verticalCuts.length <= min(w - 1, 105)1 <= horizontalCuts[i] < h1 <= verticalCuts[i] < w- 题目数据保证
horizontalCuts中的所有元素各不相同 - 题目数据保证
verticalCuts中的所有元素各不相同
解题思路
方法一：排序
我们先分别对 horizontalCuts 和 verticalCuts 排序，然后分别遍历两个数组，计算相邻两个元素的最大差值，分别记为 和 ，最后返回 即可。
注意要考虑边界情况，即 horizontalCuts 和 verticalCuts 的首尾元素。
时间复杂度 ，空间复杂度 。其中 和 分别为 horizontalCuts 和 verticalCuts 的长度。
class Solution:
def maxArea(
self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]
) -> int:
horizontalCuts.extend([0, h])
verticalCuts.extend([0, w])
horizontalCuts.sort()
verticalCuts.sort()
x = max(b - a for a, b in pairwise(horizontalCuts))
y = max(b - a for a, b in pairwise(verticalCuts))
return (x * y) % (10**9 + 7)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Does the candidate recognize that sorting is a key step?
- question_mark
Can the candidate identify the greedy choice behind the problem?
- question_mark
Does the candidate handle the modulo operation correctly when computing the area?
常见陷阱
外企场景- error
Forgetting to sort the cuts, which leads to incorrect gap calculations.
- error
Overcomplicating the solution by trying to evaluate all possible sub-areas, instead of focusing on maximum gap differences.
- error
Neglecting the modulo operation, causing overflow issues when the area is large.
进阶变体
外企场景- arrow_right_alt
What happens if the cuts are in descending order? The sorting step will still handle it correctly.
- arrow_right_alt
How does this solution scale when the number of cuts is very large? The time complexity remains efficient due to sorting.
- arrow_right_alt
What if there are no vertical or horizontal cuts? The maximum area would be the full area of the cake.