切割后面积最大的蛋糕【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)); } }
复杂度
时间复杂度：O ( n log n )
空间复杂度：O ( log n )
