算法如何处理多个标准

Question

在数组 A[n] 中找到 2 个矩形 A[i] 和 A[j] 矩形使得 A[i].width > A[j].width 和 A[i].length - A[j] .length 是最长的。

有没有办法将复杂度降低到 O(nlogn)？我找不到对第二个矩形进行 O(logn) 搜索的方法。由于 2 个标准彼此完全相反的可能性，排序似乎在这里没有帮助。也许我只是做错了？请指引我走向正确的道路。谢谢。

注意:作业分配使用不同的对象并使用 2 个标准而不是 3 个，但上下文是相同的。

Answer 1

由于这是家庭作业，这里是一个高级答案，实现留给 OP 解决:

按宽度升序对数组元素进行排序。然后向下扫描数组，从目前遇到的最大长度中减去当前长度。跟踪到目前为止遇到的最大差异(以及相应的 i 和 j)。完成后，您将获得最大的长度差 A[i].length-A[j].length 其中 A[i].width > A[j].width

分析:对元素进行排序需要O(n*Log(n))，所有其他步骤需要O(n)。