帮人代做静态网站多少钱,企业有哪些管理软件呢,广州市网络营销推广平台,时代汇创网站建设给你 n 个二维平面上的点 points #xff0c;其中 points[i] [xi, yi] #xff0c;请你返回两点之间内部不包含任何点的 最宽垂直区域 的宽度。
垂直区域 的定义是固定宽度#xff0c;而 y 轴上无限延伸的一块区域#xff08;也就是高度为无穷大#xff09;。 最宽垂直区…给你 n 个二维平面上的点 points 其中 points[i] [xi, yi] 请你返回两点之间内部不包含任何点的 最宽垂直区域 的宽度。
垂直区域 的定义是固定宽度而 y 轴上无限延伸的一块区域也就是高度为无穷大。 最宽垂直区域 为宽度最大的一个垂直区域。
请注意垂直区域 边上 的点 不在 区域内。
示例 1
输入points [[8,7],[9,9],[7,4],[9,7]] 输出1 解释红色区域和蓝色区域都是最优区域。 示例 2
输入points [[3,1],[9,0],[1,0],[1,4],[5,3],[8,8]] 输出3
提示
n points.length 2 n 105 points[i].length 2 0 xi, yi 109
法一排序后遍历一遍即可
class Solution {
public:int maxWidthOfVerticalArea(vectorvectorint points) {sort(points.begin(), points.end(), [] (vectorint left, vectorint right) {return left[0] right[0];});int ans points[1][0] - points[0][0];for (int i 2; i points.size(); i){if (points[i][0] - points[i - 1][0] ans){ans points[i][0] - points[i - 1][0];}}return ans;}
};如果points的长度为n此算法时间复杂度为O(nlogn)空间复杂度为O(1)。
法二将法一中的sort替换为自己写的快排
class Solution {
public:int maxWidthOfVerticalArea(vectorvectorint points) {quickQort(points, 0, points.size() - 1);int ans points[1][0] - points[0][0];for (int i 2; i points.size(); i){if (points[i][0] - points[i - 1][0] ans){ans points[i][0] - points[i - 1][0];}}return ans;}private:void quickQort(vectorvectorint points, int begin, int end){if (begin end){return;}int divider begin - 1;for (int i begin; i end - 1; i){if (points[i][0] points[end][0]){divider;swap(points[i], points[divider]);}}swap(points[divider 1], points[end]);quickQort(points, begin, divider);quickQort(points, divider 2, end);}
};如果points的长度为n此算法时间复杂度为O(nlogn)空间复杂度为O(1)。
