切割后面积最大的蛋糕

标签: 贪心 数组 排序

难度: Medium

矩形蛋糕的高度为 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 <= 109
  • 1 <= horizontalCuts.length <= min(h - 1, 105)
  • 1 <= verticalCuts.length <= min(w - 1, 105)
  • 1 <= horizontalCuts[i] < h
  • 1 <= verticalCuts[i] < w
  • 题目数据保证 horizontalCuts 中的所有元素各不相同
  • 题目数据保证 verticalCuts 中的所有元素各不相同

Submission

运行时间: 71 ms

内存: 26.6 MB

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        horizontalCuts.append(h) or verticalCuts.append(w)
        x0 = y0 = 0
        return max(-x0 + (x0 := x) for x in sorted(verticalCuts)) * max(-y0 + (y0 := y) for y in sorted(horizontalCuts)) % 1000000007

Explain

首先，解题思路是确定蛋糕切割后各部分的最大面积。为此，需要找到最大的水平和最大的竖直切割间隔。这可以通过先对水平和竖直切割位置进行排序，然后计算相邻切割位置之间的最大间隔来实现。首先将蛋糕的边界宽高添加到切割数组中，然后对这些数组排序。遍历排序后的数组，计算各个相邻切割点之间的间距，找到最大值。最后，将找到的最大水平间隔与最大竖直间隔相乘，得到可能的最大面积。因为结果可能非常大，所以最后结果需要对 10^9 + 7 取余。

时间复杂度: O(m log m + n log n)

空间复杂度: O(1)

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        # 添加蛋糕的边界宽高到切割数组中
        horizontalCuts.append(h)
        verticalCuts.append(w)
        x0 = y0 = 0
        # 计算最大的竖直切割间隔
        max_width = max(-x0 + (x0 := x) for x in sorted(verticalCuts))
        # 计算最大的水平切割间隔
        max_height = max(-y0 + (y0 := y) for y in sorted(horizontalCuts))
        # 计算最大面积并取模
        return (max_width * max_height) % 1000000007

Explore

将蛋糕的总宽度和高度加入到切割点数组中是为了包括蛋糕的边缘部分在内的所有可能的切割区间。如果不加入这些边界值，我们将无法计算位于蛋糕边缘到最近切割点之间的区间，这可能导致忽略实际上可能是最大的一个或多个切割区间。例如，如果最后一个切割点到蛋糕的右边缘或下边缘的距离是最大的间隔，不加入蛋糕的总宽度和高度则无法考虑这部分，从而无法得到正确的最大面积。

表达式`-x0 + (x0 := x)`是使用Python的赋值表达式（自Python 3.8引入的'walrus operator' `:=`）来计算两个相邻切割点之间的间隔。在这个表达式中，`x0`初始设置为0，`-x0 + (x0 := x)`首先将`x0`的当前值（初始为0）从`x`（当前切割点的位置）中减去，然后更新`x0`为当前的`x`。这种方式允许在单个表达式中同时进行差值计算和变量更新，使代码更紧凑且效率较高，避免了额外的行或变量声明，特别适合于遍历排序后的数组并计算连续元素的差值。

选择10^9 + 7作为模数是因为它是一个大的素数，常用于计算机编程中的模运算，尤其是在竞赛编程和算法设计中，以避免整数溢出并保持结果的稳定性和一致性。此外，由于10^9 + 7接近于最大的32位整数，它可以最大化利用该数据类型的范围。使用素数作为模数在数学上也有好处，例如在模算术中通常可以保证更好的分布性质。

为了确保在乘法计算中不发生整数溢出，可以采用模运算的技巧。在计算最大面积时，由于面积的值可能非常大，每次进行乘法计算之后立即对10^9 + 7取余，可以确保结果始终在安全的整数范围内。这种方法不仅可以防止溢出，还可以确保结果的大小始终受到控制，从而可以安全地存储和处理这些值。