如何快速找到生成最大斜率的对应点？优化O(n²)算法方案咨询

预处理：构建上凸壳 #

先把所有点处理成无冗余的候选集，核心是构建上凸壳：

1. 排序去重：将所有点按x坐标升序排列；若x相同，仅保留y值最大的点（x相同的点无法满足x2 < x1，且y值更小的点完全没有利用价值）。
2. 栈式构建凸壳：遍历排序后的点，用栈结构维护上凸壳：
   • 取当前点P，检查栈顶的两个点A、B（栈顶为B，前一个元素为A）：若AB的斜率 ≤ BP的斜率，说明B是冗余点——后续所有x大于P.x的点，选P的斜率都会比选B更大，直接弹出B。
   • 重复上述判断，直到栈中不足两个点，或AB的斜率 > BP的斜率，再将P压入栈。
   • 最终栈内的点构成上凸壳，具备x递增、相邻点斜率单调递减的性质，所有无用冗余点已被剔除。

单查询操作 #

针对每个目标点Q(x1, y1)，按以下步骤找最优解：

1. 缩小候选范围：由于凸壳的x坐标递增，用二分查找找到凸壳中最后一个x < x1的点，得到候选范围为凸壳的前k+1个点（索引0到k）。
2. 筛选符合y条件的点：在0到k的范围内，用二分查找筛选出所有y2 ≥ y1的点（凸壳的y值可能有波动，但二分依然可行）。
3. 定位最大斜率点：因为凸壳相邻点的斜率单调递减，Q到凸壳各点的斜率会形成单峰序列（先递增后递减），用三分查找可快速定位斜率最大的点；也可利用凸壳性质，通过二分查找斜率变化的拐点，效率一致。

复杂度分析 #

• 排序耗时O(n log n)，凸壳构建耗时O(n)（每个点入栈、出栈最多一次），预处理总时间为O(n log n)。
• 每个查询耗时O(log n)，整体总时间复杂度为O(n log n)，远优于暴力解法的O(n²)，适合处理大数据量的点集。

特殊情况处理 #

• 若候选范围内没有满足y2 ≥ y1的点，直接返回无符合条件的点即可。
• 若多个点的斜率相同，可根据需求任选其一。

内容的提问来源于stack exchange，提问作者mostVegetable