1465. 切割后面积最大的蛋糕

1465. 切割后面积最大的蛋糕

难度: 中等

来源: 每日一题 2023.10.27

---

矩形蛋糕的高度为 h 且宽度为 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 
解释：上图所示的矩阵蛋糕中，红色线表示水平和竖直方向上的切口。切割蛋糕后，绿色的那份蛋糕面积最大。
1
2
3

示例 2：

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

示例 3：

输入：h = 5, w = 4, horizontalCuts = [3], verticalCuts = [3]
输出：9
1
2

提示：

• 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 中的所有元素各不相同

class Solution {
    public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {

    }
}
1
2
3
4
5

分析与题解

---

• 模拟法

  当理解题意时, 这个题目其实非常的简单, 我们需要找的是什么? 不管是横向切还是纵向切, 我们需要找到 所有相邻的两刀最大的间隔. 然后横向间距与纵向间距相乘就是题目的题解结果.

  接下来, 我们就一起看一下整个题目的题解过程, 为了减少遍历次数, 我们需要把横向数组和纵向数组首先进行一次排序.

  Arrays.sort(horizontalCuts);
  Arrays.sort(verticalCuts);
  1
  2

  然后我们就需要寻找最大边距, 这里有三种情况需要讨论

  • 第一刀: 对于第一刀, 我们要考虑与 0 的关系.

    maxItemWidth = Math.max(verticalCuts[i], maxItemWidth);
    1

  • 最后一刀到边界: 这个也需要特殊考虑.

    maxItemWidth = Math.max(w - verticalCuts[verticalCuts.length - 1], maxItemWidth);
    1

  • 其他刀: 其他刀我们只要考虑它和前一刀的情况即可.

    maxItemWidth = Math.max(verticalCuts[i] - verticalCuts[i - 1], maxItemWidth);
    1

  求出 maxItemWidth 和 maxItemHeight 之后, 我们就可以求出结果来. 当然了, 要进行取模操作.

  int result = (int)(maxItemWidth * maxItemHeight % 1000000007);
  1

  接下来, 我们就看一下整体的题解过程.

  class Solution {
      public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
          Arrays.sort(horizontalCuts);
          Arrays.sort(verticalCuts);
          long maxItemWidth = 0;
          long maxItemHeight = 0;
          for(int i = 0; i <= verticalCuts.length; i++) {
              if (i == 0) {
                  maxItemWidth = Math.max(verticalCuts[i], maxItemWidth);
              } else if (i == verticalCuts.length) {
                  maxItemWidth = Math.max(w - verticalCuts[verticalCuts.length - 1], maxItemWidth);
              }  else {
                  maxItemWidth = Math.max(verticalCuts[i] - verticalCuts[i - 1], maxItemWidth);
              }
          }
          for(int i = 0; i <= horizontalCuts.length; i++) {
              if (i == 0) {
                  maxItemHeight = Math.max(horizontalCuts[i], maxItemHeight);
              } else if (i == horizontalCuts.length) {
                  maxItemHeight = Math.max(h - horizontalCuts[horizontalCuts.length - 1], maxItemHeight);
              }  else {
                  maxItemHeight = Math.max(horizontalCuts[i] - horizontalCuts[i - 1], maxItemHeight);
              }
          }
          int result = (int)(maxItemWidth * maxItemHeight % 1000000007);
          return result;
      }
  }
  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
  27
  28

  
  

  复杂度分析:

  • 时间复杂度: O(2n + 2logn), 排序的时间复杂度是 logn, 遍历的时间复杂度是 n
  • 空间复杂度: O(2logn), 排序的空间复杂度是 logn

  结果如下所示.