[leetcode] 1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts

[leetcode] 1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts

Description

Given a rectangular cake with height h and width w, and two arrays of integers horizontalCuts and verticalCuts where horizontalCuts[i] is the distance from the top of the rectangular cake to the ith horizontal cut and similarly, verticalCuts[j] is the distance from the left of the rectangular cake to the jth vertical cut.

Return the maximum area of a piece of cake after you cut at each horizontal and vertical position provided in the arrays horizontalCuts and verticalCuts. Since the answer can be a huge number, return this modulo 10^9 + 7.

Example 1:

Input: h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]Output: 4 Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts. After you cut the cake, the green piece of cake has the maximum area.

Example 2:

Input: h = 5, w = 4, horizontalCuts = [3,1], verticalCuts = [1]Output: 6Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts. After you cut the cake, the green and yellow pieces of cake have the maximum area.

Example 3:

Input: h = 5, w = 4, horizontalCuts = [3], verticalCuts = [3]Output: 9

Constraints:

2 <= h, w <= 10^91 <= horizontalCuts.length < min(h, 10^5)1 <= verticalCuts.length < min(w, 10^5)1 <= horizontalCuts[i] < h1 <= verticalCuts[i] < wIt is guaranteed that all elements in horizontalCuts are distinct.It is guaranteed that all elements in verticalCuts are distinct.

分析

题目的意思是：给定两个矩阵，分别代表竖线和横线，问横线和竖线围城的最大的区域的面积。这道题如果暴力破解的话，我觉得肯定超时，需要找规律，无论添加怎样多的横线和竖线，最大区域是横坐标间隔最大，竖坐标间隔最大的区域，这样思路就来了，找出间隔最大的区间然后相乘就行了。我的做法也很简单，把坐标排序一下，然后找出最大的间隔区间，相乘就ok了。我看了一下其他人的解法，发现跟我差不多，见参考文献。

代码

class Solution: def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int: m=len(horizontalCuts) horizontalCuts.sort() maxH=horizontalCuts[0]-0 for i in range(m-1): maxH=max(maxH,horizontalCuts[i+1]-horizontalCuts[i]) maxH=max(maxH,h-horizontalCuts[m-1]) n=len(verticalCuts) verticalCuts.sort() maxW=verticalCuts[0]-0 for j in range(n-1): maxW=max(maxW,verticalCuts[j+1]-verticalCuts[j]) maxW=max(maxW,w-verticalCuts[n-1]) return (maxW*maxH)%(10**9+7)

参考文献

​​[LeetCode] python faster then 96%​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。