下标对中的最大距离

记牢:两指针 i、j 都只向右。nums1[i] ≤ nums2[j] 就记距离 j 减 i 再让 j 右移(拉大距离);nums1[i] 大于 nums2[j] 就让 i 右移(这个 i 再也配不上更靠后的 j)。

总览 · 两个非递增数组配对：先看清画面。上面这排格子是 nums1 = 7,5,5,2,1,右边面板是 nums2 = 9,8,8,7,3,2,下标从 0 开始,两个数组都非递增。我们要挑一对下标 i 和 j,i 不超过 j,并且 nums1 在 i 处的值不超过 nums2 在 j 处的值,让距离 j 减 i 最大。上排的紫色箭头代表指针 i,右边面板里高亮的那一行代表指针 j。两个指针都从头开始,谁也不回头。

摆好两个指针 · i=0,j=0：开始配对。指针 i 站在 nums1 的头部下标 0,值是 7;指针 j 站在 nums2 的头部下标 0,值是 9。思路很简单,每一步就比一比 nums1 在 i 处的值和 nums2 在 j 处的值:配得上就记距离再让 j 往后拉,配不上就让 i 往后挪。当前最大距离先记成 0。开始一步步走。

第一步 · 比一比 i=0,j=0：第一步。指针 i 在 nums1 下标 0,值是 7;指针 j 在 nums2 下标 0,值是 9。把这两个值比一比,看 nums1 在 i 处的 7 能不能不超过 nums2 在 j 处的 9。看起来 7 不大于 9,像是能配上,下一帧确认。

第一步 · 有效对 距离 0：确认:7 不大于 9,这是一对有效对,而且此时 i 等于 0 不超过 j 等于 0,下标要求也满足。距离是 j 减 i 等于 0。不过 0 没有超过已经拿到的最大距离 0,最大距离保持不变。接着把 j 右移一格,看能不能让距离更大。

第二步 · 比一比 i=0,j=1：第二步。指针 i 在 nums1 下标 0,值是 7;指针 j 在 nums2 下标 1,值是 8。把这两个值比一比,看 nums1 在 i 处的 7 能不能不超过 nums2 在 j 处的 8。看起来 7 不大于 8,像是能配上,下一帧确认。

第二步 · 有效对 距离 1：确认:7 不大于 8,这是一对有效对,而且此时 i 等于 0 不超过 j 等于 1,下标要求也满足。距离是 j 减 i 等于 1。这比之前的最大距离还大,最大距离刷新成 1。接着把 j 右移一格,看能不能让距离更大。

第三步 · 比一比 i=0,j=2：第三步。指针 i 在 nums1 下标 0,值是 7;指针 j 在 nums2 下标 2,值是 8。把这两个值比一比,看 nums1 在 i 处的 7 能不能不超过 nums2 在 j 处的 8。看起来 7 不大于 8,像是能配上,下一帧确认。

第三步 · 有效对 距离 2：确认:7 不大于 8,这是一对有效对,而且此时 i 等于 0 不超过 j 等于 2,下标要求也满足。距离是 j 减 i 等于 2。这比之前的最大距离还大,最大距离刷新成 2。接着把 j 右移一格,看能不能让距离更大。

第四步 · 比一比 i=0,j=3：第四步。指针 i 在 nums1 下标 0,值是 7;指针 j 在 nums2 下标 3,值是 7。把这两个值比一比,看 nums1 在 i 处的 7 能不能不超过 nums2 在 j 处的 7。看起来 7 不大于 7,像是能配上,下一帧确认。

第四步 · 有效对 距离 3：确认:7 不大于 7,这是一对有效对,而且此时 i 等于 0 不超过 j 等于 3,下标要求也满足。距离是 j 减 i 等于 3。这比之前的最大距离还大,最大距离刷新成 3。接着把 j 右移一格,看能不能让距离更大。

第五步 · 比一比 i=0,j=4：第五步。指针 i 在 nums1 下标 0,值是 7;指针 j 在 nums2 下标 4,值是 3。把这两个值比一比,看 nums1 在 i 处的 7 能不能不超过 nums2 在 j 处的 3。看起来 7 比 3 大,怕是配不上,下一帧见分晓。

第五步 · 配不上 i 右移：确认:7 比 3 大,配不上,这一格标红。关键在于 nums2 是非递增的,j 再往后只会更小,更不可能不小于 7,所以这个 nums1 在 i 处的 7 已经没希望配上任何更靠后的 j 了。那就把 i 右移一格,换一个更小的 nums1 值来试。j 留在原地不动,最大距离仍是 3。

第六步 · 比一比 i=1,j=4：第六步。指针 i 在 nums1 下标 1,值是 5;指针 j 在 nums2 下标 4,值是 3。把这两个值比一比,看 nums1 在 i 处的 5 能不能不超过 nums2 在 j 处的 3。看起来 5 比 3 大,怕是配不上,下一帧见分晓。

第六步 · 配不上 i 右移：确认:5 比 3 大,配不上,这一格标红。关键在于 nums2 是非递增的,j 再往后只会更小,更不可能不小于 5,所以这个 nums1 在 i 处的 5 已经没希望配上任何更靠后的 j 了。那就把 i 右移一格,换一个更小的 nums1 值来试。j 留在原地不动,最大距离仍是 3。

第七步 · 比一比 i=2,j=4：第七步。指针 i 在 nums1 下标 2,值是 5;指针 j 在 nums2 下标 4,值是 3。把这两个值比一比,看 nums1 在 i 处的 5 能不能不超过 nums2 在 j 处的 3。看起来 5 比 3 大,怕是配不上,下一帧见分晓。

第七步 · 配不上 i 右移：确认:5 比 3 大,配不上,这一格标红。关键在于 nums2 是非递增的,j 再往后只会更小,更不可能不小于 5,所以这个 nums1 在 i 处的 5 已经没希望配上任何更靠后的 j 了。那就把 i 右移一格,换一个更小的 nums1 值来试。j 留在原地不动,最大距离仍是 3。

第八步 · 比一比 i=3,j=4：第八步。指针 i 在 nums1 下标 3,值是 2;指针 j 在 nums2 下标 4,值是 3。把这两个值比一比,看 nums1 在 i 处的 2 能不能不超过 nums2 在 j 处的 3。看起来 2 不大于 3,像是能配上,下一帧确认。

第八步 · 有效对 距离 1：确认:2 不大于 3,这是一对有效对,而且此时 i 等于 3 不超过 j 等于 4,下标要求也满足。距离是 j 减 i 等于 1。不过 1 没有超过已经拿到的最大距离 3,最大距离保持不变。接着把 j 右移一格,看能不能让距离更大。

第九步 · 比一比 i=3,j=5：第九步。指针 i 在 nums1 下标 3,值是 2;指针 j 在 nums2 下标 5,值是 2。把这两个值比一比,看 nums1 在 i 处的 2 能不能不超过 nums2 在 j 处的 2。看起来 2 不大于 2,像是能配上,下一帧确认。

第九步 · 有效对 距离 2：确认:2 不大于 2,这是一对有效对,而且此时 i 等于 3 不超过 j 等于 5,下标要求也满足。距离是 j 减 i 等于 2。不过 2 没有超过已经拿到的最大距离 3,最大距离保持不变。接着把 j 右移一格,看能不能让距离更大。

扫描结束 · 指针走到头：两个指针里,j 已经越过 nums2 的末尾,循环停下来。整趟下来 i 只往右走、j 也只往右走,两个指针各自从头扫到尾,合起来最多走 m 加 n 步。现在把这一路记录到的最大距离揭晓出来。

揭晓 · 最优对距离 3：把最好的那一对摆出来。指针 i 在下标 0,nums1 值是 7;指针 j 在下标 3,nums2 值是 7。7 不超过 7,下标 0 也不超过 3,是一对合法有效对,距离 j 减 i 等于 3。这就是全程能拿到的最大距离。后面 i 挪到 3 之后虽然也能配上,但那时 j 只差 1 到 2,距离都比 3 小。

完成 · 最大距离 = 3：收个尾。整道题靠两个只往右走的指针:配得上就记距离再把 j 往后拉去争取更大距离,配不上就把 i 往后挪去换个更小的值。nums1 = 7,5,5,2,1 配 nums2 = 9,8,8,7,3,2,最终最大距离是 3。两个指针合起来只扫了一遍,线性时间、常数额外空间,又快又省。

边界:2,2,2 配 10,10,1 最大距离 1;30,29,19,5 配全 25 要先把 i 推过配不上的大值、答案 2;nums1 全大于 nums2 时无有效对返回 0。

面试重点:两数组非递增,配上就固定 i 推 j 争最大距离、配不上就永久弃 i,i、j 各单调一遍不漏不重;双指针与二分同解、时间 O(m+n) 优于 O(m log n);i ≤ j 的下标约束是双指针成立的前提。