企业网站建设和网络营销的关系,提供模板网站制作多少钱,12345律师免费咨询,自然景观网站模板切割后面积最大的蛋糕【LC1465】 矩形蛋糕的高度为 h 且宽度为 w#xff0c;给你两个整数数组 horizontalCuts 和 verticalCuts#xff0c;其中#xff1a; horizontalCuts[i] 是从矩形蛋糕顶部到第 i 个水平切口的距离verticalCuts[j] 是从矩形蛋糕的左侧到第 j 个竖直切口…切割后面积最大的蛋糕【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 ) \mathcal{O}(n \log {n} ) O(nlogn)空间复杂度 O ( log n ) \mathcal{O}(\log {n} ) O(logn)
