Last Updated on 2023-12-21 by Clay
題目
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.length2 <= n <= 105points[i].length == 20 <= 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