【每日一题Day360】LC1465切割后面积最大的蛋糕 | 贪心

切割后面积最大的蛋糕【LC1465】

矩形蛋糕的高度为 h 且宽度为 w，给你两个整数数组 horizontalCuts 和 verticalCuts，其中：

• horizontalCuts[i] 是从矩形蛋糕顶部到第 i 个水平切口的距离
• verticalCuts[j] 是从矩形蛋糕的左侧到第 j 个竖直切口的距离

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

• 思路

  切分结束后，每块蛋糕的长/宽由相邻两刀的距离决定，而面积为长*宽，长和宽为独立的两个分量，因此可以求出水平方向和垂直方向相邻两刀最长的距离，相乘得到最大面积

  • 局部最优：使蛋糕的长/宽较长
  • 全局最优：面积最大

• 实现

  class Solution {
      public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
          int n = horizontalCuts.length, m = verticalCuts.length;
          Arrays.sort(horizontalCuts);
          Arrays.sort(verticalCuts);
          int maxH = Math.max(horizontalCuts[0], h - horizontalCuts[n - 1]);
          int maxW = Math.max(verticalCuts[0], w - verticalCuts[m - 1]);
          for (int i = 0; i < n - 1; i++){
              maxH = Math.max(maxH, horizontalCuts[i + 1] - horizontalCuts[i]);
          }
          for (int i = 0; i < m - 1; i++){
              maxW = Math.max(maxW, verticalCuts[i + 1] - verticalCuts[i]);
          }
          return (int)((1L * maxH * maxW) % (int)(1e9 + 7));
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16

  • 复杂度
    • 时间复杂度：$\mathcal{O}(n\log n)$
    • 空间复杂度：$\mathcal{O}(\log n)$