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

Posted on

題目在此 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)

相關文章