【每日一题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));}
  }
  

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