如何用O(N)或O(NlogN)算法求满足a[j]>a[i]且b[j]>b[i]的最小j-i

我们要找满足a[i]<a[j]、b[i]<b[j]且i<j的最小j-i，核心是淘汰不可能成为最优解的候选下标，避免暴力遍历所有下标对：

• 维护一个候选下标列表，列表中的元素满足两个性质：
  1. 对应的a值严格递增
  2. 对应的b值严格递减
     这两个性质的作用是：如果存在两个下标i1<i2，同时满足a[i1]>=a[i2]和b[i1]>=b[i2]，则i1永远不可能成为比i2更优的解——对于任意j>i2，如果i1满足匹配条件，i2一定也满足，且j-i2更小，因此i1可以直接被淘汰。
• 遍历每个下标j时，按以下步骤处理：
  1. 先删除候选列表末尾所有a值大于等于a[j]的元素，保证列表a的递增性，此时剩下的所有候选a值都小于a[j]
  2. 由于候选列表的b值是严格递减的，我们可以通过二分查找快速找到最大的下标i满足b[i]<b[j]，如果存在这样的i，则用j-i更新全局最小差值
  3. 最后删除候选列表末尾所有b值小于等于b[j]的元素，保证列表b的递减性，再将j加入候选列表

每个下标最多被加入候选列表1次、删除1次，总操作次数为O(N)；每次二分查找的时间复杂度为O(logK)，K为候选列表的长度，最坏为O(logN)，因此整体时间复杂度为O(NlogN)，可以满足n≤10^6的性能要求。

function find_min_diff(a, b, n):
    candidates = empty list
    min_diff = infinity
    for j from 1 to n:
        // 步骤1：维护a的递增性，删除末尾a>=a[j]的元素
        while candidates is not empty and a[candidates[-1]] >= a[j]:
            candidates.pop()
        // 步骤2：二分找符合b[i]<b[j]的最大i
        if candidates is not empty:
            left = 0, right = len(candidates) - 1
            best_i = -1
            while left <= right:
                mid = (left + right) // 2
                if b[candidates[mid]] < b[j]:
                    best_i = candidates[mid]
                    left = mid + 1 // 找更大的i，差更小
                else:
                    right = mid - 1
            if best_i != -1:
                min_diff = min(min_diff, j - best_i)
        // 步骤3：维护b的递减性，删除末尾b<=b[j]的元素
        while candidates is not empty and b[candidates[-1]] <= b[j]:
            candidates.pop()
        candidates.append(j)
    return min_diff if min_diff != infinity else -1 // 无符合条件的对返回-1

以题目给出的示例输入为例：

N=3，a=[1,7,3]，b=[3,6,2]

1. j=1，候选列表为空，直接加入，候选列表为[1]，min_diff仍为无穷大
2. j=2，候选列表末尾a=1<7无需删除；二分查找b<6的i，得到i=1，差为1，min_diff更新为1；删除末尾b=3<=6的元素，列表为空，加入j=2，候选列表为[2]
3. j=3，候选列表末尾a=7>=3，删除后列表为空，无需查找；加入j=3，候选列表为[3]
4. 最终返回min_diff=1，和示例输出一致

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