LeetCode 筆記 - 1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts

題目在此 1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts

給定橫向切哪裡,縱向切哪裡,請給出切完後最大面積

image 36

解題思維

就橫向縱向各自找出最大的跨度在哪,然後乘起來即可

要注意的是切的座標並沒有經過排序

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:

def get_max_space(size: int, cut: List[int]) -> int:
cut.sort()

last_index = 0
result = 0
for c in cut:
if c == 0:
continue
result = max(result, c - last_index)
last_index = c

result = max(result, size - last_index)

return result

max_h = get_max_space(h, horizontalCuts)
max_w = get_max_space(w, verticalCuts)

return (max_h * max_w) % (10 ** 9 + 7)

也許你也會想看看