关于最小化(s[i]-s[j]+d)/(i-j)的线性/亚二次算法问询

给定已排序数组s与正整数d，需在i>j的约束下，最小化表达式 (s[i]-s[j]+d)/(i-j)。当前主流解法基于二分查找确定最优解边界，时间复杂度依赖于s的最大值与最小值之差，请问能否构建时间复杂度为数组规模的线性或亚二次级别的算法？

当然可以，这里提供两种符合要求的思路：

• 凸包优化（线性时间O(n)）
  先对表达式做等价变形：把 (s[i]-s[j]+d)/(i-j) 转化为求点 (i, s[i]) 与点 (j, s[j]-d) 之间斜率的最小值（或者等价的点对变形）。由于数组s是已排序的，对应的点列具有凸性，完全符合凸包trick的应用场景。
  我们可以维护一个单调的凸壳结构，遍历数组时，对每个位置i，直接在凸壳中找到能使目标斜率最小的j，这个查询过程可以通过单调队列实现，每次查询仅需O(1)时间；而构建凸壳的过程也是线性的，最终整体时间复杂度为O(n)，属于线性级别。

• 分治法（亚二次时间O(n log n)）
  采用分治策略：将数组分成左右两部分，分别求解左右子数组内部的最优解，再寻找跨左右两部分的最优解。由于数组是有序的，跨部分的候选(i,j)对可以通过有序性快速筛选，无需遍历所有可能的组合。整体时间复杂度为O(n log n)，属于亚二次级别，远优于暴力的O(n²)解法。

这两种方法都摆脱了对数组元素值域的依赖，时间复杂度仅由数组规模n决定，完全满足需求。

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