题目描述
思路解析
一句话答案：LeetCode 1855 下标对中的最大距离：合法对要 i ≤ j 且 nums1[i] ≤ nums2[j]。两数组非递增，对每个 i 二分找最靠后的合法 j，取 j - i 最大。时间 O(m log n)、空间 O(n)。
两个非递增数组里，要挑距离最大的哪种下标对
给两个非递增数组 nums1、nums2（下标从 0 起，每个数不比前一个大）。挑下标 (i, j)，同时满足 i ≤ j 和 nums1[i] ≤ nums2[j] 才算有效，距离 j - i。求最大距离，没有有效对返回 0。题面 nums1=[7,5,5,2,1]、nums2=[9,8,8,7,3,2]，答案 3。
把每个 i 都配一遍 j，为什么撑不到十万级
蛮力是双层枚举：nums1 每个 i 配 nums2 里每个 j ≥ i，逐对验 nums1[i] ≤ nums2[j]。两数组各长到 10⁵，对数是 m 乘 n 量级、逼近 10¹⁰，跑不完。若能对每个 i 一步跳到够得着的最靠后 j，就省掉这遍扫描。
两数组都非增，对每个 i 二分找最远合法 j
固定 i、记 v = nums1[i]，找满足 nums2[j] ≥ v 的最靠后 j。nums2 非递增，某位置一旦掉到 v 以下，右边只会更小、全部出局——满足条件的下标恰是从 0 起的连续前缀。一边全成立、一边全不成立的单调结构正好能二分：几步就卡到前缀最后一格，即这个 i 要的 j。
倒序数组上二分落哪，原下标怎么还原
参考代码先把 nums2 倒过来（nums2[::-1]），非递增变非递减，好套二分。对每个 v，用 bisect_left（第一个 ≥ 目标的插入位置）在倒序数组找到 pos——从 pos 起往右都 ≥ v。
再把 pos 换回原下标：倒序第 k 位对应原第 n-1-k 位，倒序里 ≥ v 的那段对应原数组 [0, n-1-pos]，最靠后即 j = len(nums2) - pos - 1。整段都没有 ≥ v 时 pos = n、j = -1，距离为负被丢掉。ans 取所有 j - i 最大。
题面这组数，每个 i 的 j 各是几
nums2=[9,8,8,7,3,2] 倒过来是 [2,3,7,8,8,9]，n=6，ans 从 0 起。
nums1[0]=7：bisect_left 在 [2,3,7,8,8,9] 找 7 落下标 2，j 为 6-2-1=3，距离 3-0=3，ans 记 3。nums1[1]=5 与 nums1[2]=5：都插在 3 和 7 间 pos=2、j 为 3，距离分别 2、1。nums1[3]=2：落最前 pos=0，j 为 5，距离 5-3=2。nums1[4]=1：pos=0、j 为 5，距离 1。五轮最大的 3 即答案。
j 平白滑到隔壁一格，多半是下标还原漏了那个 −1
最易错是还原那步：j = len(nums2) - pos - 1，漏掉 -1 会让 j 右移一格、指错位置。二是方向：非递增当成升序二分，前缀后缀全判反。还有兜底：ans 从 0 起——某个 v 谁都配不上（j = -1）距离为负，或 nums1 全大过 nums2 时，从 0 起才返回 0。
复杂度：m 个元素各做一次 O(log n) 二分，合计 O(m log n)；Python 切片把 nums2 倒过来新建长度 n 的列表，额外空间 O(n)（原地二分可降到 O(1)）。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢:两指针 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 的下标约束是双指针成立的前提。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def maxDistance(self, nums1: List[int], nums2: List[int]) -> int: ans = 0 nums2 = nums2[::-1] for i, v in enumerate(nums1): j = len(nums2) - bisect_left(nums2, v) - 1 ans = max(ans, j - i) return ans复杂度
- 时间：O(m log n)，m、n 分别是 nums1、nums2 的长度。代码区的参考写法对 nums1 里最多 m 个元素,每个都在 nums2 里做一次二分查找,每次 O(log n),合起来 O(m log n),这是代码区展示的写法的复杂度。动画演示的双指针写法,i 和 j 都只往右走、合起来最多前进 m 加 n 步,可以把整体降到 O(m+n) 的线性时间,两者答案一致
- 空间：O(1) 或 O(n)，按峰值算,而且要分语言。双指针写法只用 i、j、ans 几个变量,额外空间 O(1)。参考代码里,C++ 用 reverse 原地反转 nums2、Java 干脆不反转直接在区间上二分,这两种都是额外 O(1);唯独 Python 用切片把 nums2 倒过来时新建了一个长度为 n 的列表,额外空间是 O(n)。所以严格讲空间是 O(1),Python 的切片反转版例外要记 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么两个指针都只往右走一遍就够,不会漏掉更优的下标对?
追问这题的双指针和参考代码里的二分是什么关系,哪个更好?
追问如果把有效对的下标约束从 i ≤ j 去掉,会发生什么?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
准时到达的列车最小时速
LeetCode 1870 · 中等 · 沿着 二分套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题