X

LEETCODE 1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts 解题思路分析

题目大意:

切割后面积最大的蛋糕

矩形蛋糕的高度为 h 且宽度为 w,给你两个整数数组 horizontalCuts 和 verticalCuts,其中 horizontalCuts[i] 是从矩形蛋糕顶部到第  i 个水平切口的距离,类似地, verticalCuts[j] 是从矩形蛋糕的左侧到第 j 个竖直切口的距离。

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

示例 1:

输入:h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]
输出:4
解释:上图所示的矩阵蛋糕中,红色线表示水平和竖直方向上的切口。切割蛋糕后,绿色的那份蛋糕面积最大。

示例 2:

输入:h = 5, w = 4, horizontalCuts = [3,1], verticalCuts = [1]
输出:6
解释:上图所示的矩阵蛋糕中,红色线表示水平和竖直方向上的切口。切割蛋糕后,绿色和黄色的两份蛋糕面积最大。

示例 3:

输入:h = 5, w = 4, horizontalCuts = [3], verticalCuts = [3]
输出:9

提示:

  • 2 <= h, w <= 10^9
  • 1 <= horizontalCuts.length < min(h, 10^5)
  • 1 <= verticalCuts.length < min(w, 10^5)
  • 1 <= horizontalCuts[i] < h
  • 1 <= verticalCuts[i] < w
  • 题目数据保证 horizontalCuts 中的所有元素各不相同
  • 题目数据保证 verticalCuts 中的所有元素各不相同

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1465

解题思路分析:

本题最笨的方法即是遍历出每一个格子的面积然后取最大值。不过数据规模并不允许这个级别的时间复杂度。其实,仔细想想,本题并没有那么复杂,我们只要找出最大的横格,与最大的纵格,他们相交处的面积一定是最大的,即返回结果。

另外需要注意一点,遍历最大距离时,别忘记边界,如左边界与第1条纵切,再比如下边界与最后一条横切。

实现代码:

public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
    Arrays.sort(horizontalCuts); // 排序所有横切
    Arrays.sort(verticalCuts); // 排序所有纵切
    // 最大横切间距(默认为最大高度到最后一刀横切间距离)
    long maxH=h-horizontalCuts[horizontalCuts.length-1];
    // 最大纵切间距(默认为最大宽度到最后一刀纵切间距离)
    long maxW=w-verticalCuts[verticalCuts.length-1];
    // 循环每一纵切,找到最大纵切间距离
    for(int i=0;i<verticalCuts.length;i++){
        int width=verticalCuts[i]-(i==0?0:verticalCuts[i-1]);
        maxW=Math.max(maxW,width);
    }
    // 循环每一横切,找到最大横切间距离
    for(int i=0;i<horizontalCuts.length;i++){
        int height=horizontalCuts[i]-(i==0?0:horizontalCuts[i-1]);
        maxH=Math.max(maxH,height);
    }
    // 两者乘积为最大面积
    long area=maxW*maxH;
    return (int)(area%1000000007);
}

本题解法执行时间为14ms。

Runtime: 14 ms, faster than 79.02% of Java online submissions for Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts.

Memory Usage: 49.4 MB, less than 100.00% of Java online submissions for Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1465-maximum-area-of-a-piece-of-cake-after-horizontal-and-vertical-cuts-解题思路分析/
Categories: leetcode
kwantong: