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

- 2 minutes read - 558 words

Leetcode 1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts

題目

You are given a rectangular cake of size h x 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, and
  • 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 large number, return this modulo 109 + 7.

想法

這題看完就會發現你其實只要分別找高的最大值與寬的最大值就好了。

因為最大那塊大小就是高的最大值與寬的最大值的乘積。

找最大值的方法，以高為例：

我們就先將所有切割線做遞增排序，可以得到如下關係

  • 上方邊界
  • 第一水平切割線
  • 第二水平切割線
  • …
  • 倒數第二水平切割線
  • 倒數第一水平切割線
  • 下方邊界

遍歷跑過去找相鄰兩個距離的最大值就可以得到答案了。

而寬度也是如此。

最後再將高的最大值與寬的最大值乘起來取模 109 + 7 就好了。

實作

Javascript

var maxArea = function(h, w, horizontalCuts, verticalCuts) {
    // 先把切割線都做遞增排序
    verticalCuts.sort((a,b) => a - b);
    horizontalCuts.sort((a,b) => a - b);
    
    // 紀錄最大高度以及最大寬度，初始值設為第一條切割線到相鄰邊界的距離
    let max_height = horizontalCuts[0], max_width = verticalCuts[0];

    // 逐步看兩相鄰切割線距離，找最大高度
    for(let i = 1; i < horizontalCuts.length; i++) {
        let height = horizontalCuts[i] - horizontalCuts[i - 1];
        max_height = height > max_height ? height : max_height;
    }
    // 也要看看最後一條切割線到相鄰邊界的距離
    let height = h - horizontalCuts[horizontalCuts.length - 1];
    max_height = height > max_height ? height : max_height;
    
    // 逐步看兩相鄰切割線距離，找最大寬度
    for(let i = 1; i < verticalCuts.length; i++) {
        let width = verticalCuts[i] - verticalCuts[i - 1];
        max_width = width > max_width ? width : max_width;
    }
    // 看看最後一條切割線到相鄰邊界的距離
    let width = w - verticalCuts[verticalCuts.length - 1];
    max_width = width > max_width ? width : max_width;
    
    // 輸出最大塊面積
    return (max_height * max_width) % (1e9 + 7);
};