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

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

复杂度

时间复杂度:O ( n log ⁡ n )

空间复杂度:O ( log ⁡ n )

目录
相关文章
|
7月前
【每日一题Day312】LC2240买钢笔和铅笔的方案数 | 完全背包 数学
【每日一题Day312】LC2240买钢笔和铅笔的方案数 | 完全背包 数学
61 0
|
7月前
【每日一题Day297】LC1444切披萨的方案数 | 动态规划+二维前缀和
【每日一题Day297】LC1444切披萨的方案数 | 动态规划+二维前缀和
71 0
|
7月前
|
算法
【每日一题Day363】LC275H 指数Ⅱ | 二分答案
【每日一题Day363】LC275H 指数Ⅱ | 二分答案
55 0
|
7月前
【每日一题Day302】LC849到最近的人的最大距离 | 贪心+分类讨论
【每日一题Day302】LC849到最近的人的最大距离 | 贪心+分类讨论
55 0
|
7月前
|
机器学习/深度学习
【每日一题Day125】LC1326灌溉花园的最少水龙头数目 | 动态规划 贪心
【每日一题Day125】LC1326灌溉花园的最少水龙头数目 | 动态规划 贪心
55 0
【动态规划刷题 6】 删除并获得点数&& 粉刷房子
【动态规划刷题 6】 删除并获得点数&& 粉刷房子
|
7月前
|
存储 Rust 算法
LeetCode 1465. 切割后面积最大的蛋糕
LeetCode 1465. 切割后面积最大的蛋糕
52 1
|
7月前
代码随想录Day29 贪心04 LeetCode T860 柠檬水找零 T406 根据身高重建队列 T452 用最少得箭引爆气球
代码随想录Day29 贪心04 LeetCode T860 柠檬水找零 T406 根据身高重建队列 T452 用最少得箭引爆气球
42 0
|
7月前
【每日一题Day314】LC1921消灭怪物的最大数量 | 贪心+排序
【每日一题Day314】LC1921消灭怪物的最大数量 | 贪心+排序
49 0
|
7月前
【每日一题Day165】LC1039多边形三角剖分的最低得分 | 区间dp
【每日一题Day165】LC1039多边形三角剖分的最低得分 | 区间dp
58 0