Skip to content

LeetCode: 1637 Widest Vetical Area Between Two Points Containing No Points 解題紀錄

題目

Given n points on a 2D plane where points[i] = [xi, yi], Return the widest vertical area between two points such that no points are inside the area.

A vertical area is an area of fixed-width extending infinitely along the y-axis (i.e., infinite height). The widest vertical area is the one with the maximum width.

Note that points on the edge of a vertical area are not considered included in the area.

Example 1:

​Input: points = [[8,7],[9,9],[7,4],[9,7]] Output: 1 Explanation: Both the red and the blue area are optimal.

Example 2:Input: points = [[3,1],[9,0],[1,0],[1,4],[5,3],[8,8]] Output: 3

Constraints:

  • n == points.length
  • 2 <= n <= 105
  • points[i].length == 2
    • 0 <= xi, yi <= 109

解題思路

這個題目讓我看不懂很長一段時間，最後還是問了 GPT-4 讓他解釋給我聽。一聽之下我才明白原來給定 Y 值是個障眼法，我們只需要判斷相鄰的兩個點之間最大的距離即可，並且這中間完全不能有其他點，簡單來說就是如果三個點位置分別為 [1, 2, 3]，我們不能說 1 到 3 之間的距離是 2。

一開始我很簡單地使用內建的排序，然後驚訝地發現這樣做的方法是很慢的。之後才想通，完全是因為使用內建的排序的話，會連 y 值都一起考慮進去，造成不必要的計算浪費。

最後會發現，先使用一個陣列把 x 全部儲存起來，接著再進行排序、比較相鄰兩點的最大值，才會是最快的作法。唯一的問題就是這樣一來我們需要額外的空間，從 O(1) 變成 O(n) 了。


C++ 範例程式碼

class Solution {
public:
    Solution() {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
    }

    int maxWidthOfVerticalArea(vector<vector<int>>& points) {
        // Init
        vector<int> x;
        for (auto& point: points) {
            x.emplace_back(point[0]);
        }

        // Sort
        sort(x.begin(), x.end());

        // Find the widest distance
        int widest = 0;
        for (int i=1; i<x.size(); ++i) {
            widest = max(widest, x[i] - x[i-1]);
        }

        return widest;
    }
};



Python 範例程式碼

class Solution:
    def maxWidthOfVerticalArea(self, points: List[List[int]]) -> int:
        # Init
        x = [_x for _x, _y in points]

        # Sort
        x = sorted(x)

        # Find the widest distance
        widest = 0
        for i in range(1, len(x)):
            widest = max(widest, x[i] - x[i-1])

        return widest


References

Read More

Tags:

Leave a Reply