下标对中的最大距离 图解题解
这道题到底在问什么
- 输入
- nums1=[55,30,5,4,2], nums2=[100,20,10,10,5]
- 输出
- 2
- 输入
- nums1=[2,2,2], nums2=[10,10,1]
- 输出
- 1
- 输入
- nums1=[7,5,5,2,1], nums2=[9,8,8,7,3,2]
- 输出
- 3
最优解：一步一步想明白
- 3记牢:两指针 i、j 都只向右。nums1[i] ≤ nums2[j] 就记距离 j 减 i 再让 j 右移(拉大距离);nums1[i] 大于 nums2[j] 就让 i 右移(这个 i 再也配不上更靠后的 j)。
- 4先看清画面。上面这排格子是 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。两个指针都从头开始,谁也不回头。
- 5开始配对。指针 i 站在 nums1 的头部下标 0,值是 7;指针 j 站在 nums2 的头部下标 0,值是 9。思路很简单,每一步就比一比 nums1 在 i 处的值和 nums2 在 j 处的值:配得上就记距离再让 j 往后拉,配不上就让 i 往后挪。当前最大距离先记成 0。开始一步步走。
- 6第一步。指针 i 在 nums1 下标 0,值是 7;指针 j 在 nums2 下标 0,值是 9。把这两个值比一比,看 nums1 在 i 处的 7 能不能不超过 nums2 在 j 处的 9。看起来 7 不大于 9,像是能配上,下一帧确认。
- 7确认:7 不大于 9,这是一对有效对,而且此时 i 等于 0 不超过 j 等于 0,下标要求也满足。距离是 j 减 i 等于 0。不过 0 没有超过已经拿到的最大距离 0,最大距离保持不变。接着把 j 右移一格,看能不能让距离更大。
- 8第二步。指针 i 在 nums1 下标 0,值是 7;指针 j 在 nums2 下标 1,值是 8。把这两个值比一比,看 nums1 在 i 处的 7 能不能不超过 nums2 在 j 处的 8。看起来 7 不大于 8,像是能配上,下一帧确认。
- 9确认:7 不大于 8,这是一对有效对,而且此时 i 等于 0 不超过 j 等于 1,下标要求也满足。距离是 j 减 i 等于 1。这比之前的最大距离还大,最大距离刷新成 1。接着把 j 右移一格,看能不能让距离更大。
- 10第三步。指针 i 在 nums1 下标 0,值是 7;指针 j 在 nums2 下标 2,值是 8。把这两个值比一比,看 nums1 在 i 处的 7 能不能不超过 nums2 在 j 处的 8。看起来 7 不大于 8,像是能配上,下一帧确认。
- 11确认:7 不大于 8,这是一对有效对,而且此时 i 等于 0 不超过 j 等于 2,下标要求也满足。距离是 j 减 i 等于 2。这比之前的最大距离还大,最大距离刷新成 2。接着把 j 右移一格,看能不能让距离更大。
- 12第四步。指针 i 在 nums1 下标 0,值是 7;指针 j 在 nums2 下标 3,值是 7。把这两个值比一比,看 nums1 在 i 处的 7 能不能不超过 nums2 在 j 处的 7。看起来 7 不大于 7,像是能配上,下一帧确认。
- 13确认:7 不大于 7,这是一对有效对,而且此时 i 等于 0 不超过 j 等于 3,下标要求也满足。距离是 j 减 i 等于 3。这比之前的最大距离还大,最大距离刷新成 3。接着把 j 右移一格,看能不能让距离更大。
- 14第五步。指针 i 在 nums1 下标 0,值是 7;指针 j 在 nums2 下标 4,值是 3。把这两个值比一比,看 nums1 在 i 处的 7 能不能不超过 nums2 在 j 处的 3。看起来 7 比 3 大,怕是配不上,下一帧见分晓。
- 15确认:7 比 3 大,配不上,这一格标红。关键在于 nums2 是非递增的,j 再往后只会更小,更不可能不小于 7,所以这个 nums1 在 i 处的 7 已经没希望配上任何更靠后的 j 了。那就把 i 右移一格,换一个更小的 nums1 值来试。j 留在原地不动,最大距离仍是 3。
- 16第六步。指针 i 在 nums1 下标 1,值是 5;指针 j 在 nums2 下标 4,值是 3。把这两个值比一比,看 nums1 在 i 处的 5 能不能不超过 nums2 在 j 处的 3。看起来 5 比 3 大,怕是配不上,下一帧见分晓。
- 17确认:5 比 3 大,配不上,这一格标红。关键在于 nums2 是非递增的,j 再往后只会更小,更不可能不小于 5,所以这个 nums1 在 i 处的 5 已经没希望配上任何更靠后的 j 了。那就把 i 右移一格,换一个更小的 nums1 值来试。j 留在原地不动,最大距离仍是 3。
- 18第七步。指针 i 在 nums1 下标 2,值是 5;指针 j 在 nums2 下标 4,值是 3。把这两个值比一比,看 nums1 在 i 处的 5 能不能不超过 nums2 在 j 处的 3。看起来 5 比 3 大,怕是配不上,下一帧见分晓。
- 19确认:5 比 3 大,配不上,这一格标红。关键在于 nums2 是非递增的,j 再往后只会更小,更不可能不小于 5,所以这个 nums1 在 i 处的 5 已经没希望配上任何更靠后的 j 了。那就把 i 右移一格,换一个更小的 nums1 值来试。j 留在原地不动,最大距离仍是 3。
- 20第八步。指针 i 在 nums1 下标 3,值是 2;指针 j 在 nums2 下标 4,值是 3。把这两个值比一比,看 nums1 在 i 处的 2 能不能不超过 nums2 在 j 处的 3。看起来 2 不大于 3,像是能配上,下一帧确认。
- 21确认:2 不大于 3,这是一对有效对,而且此时 i 等于 3 不超过 j 等于 4,下标要求也满足。距离是 j 减 i 等于 1。不过 1 没有超过已经拿到的最大距离 3,最大距离保持不变。接着把 j 右移一格,看能不能让距离更大。
- 22第九步。指针 i 在 nums1 下标 3,值是 2;指针 j 在 nums2 下标 5,值是 2。把这两个值比一比,看 nums1 在 i 处的 2 能不能不超过 nums2 在 j 处的 2。看起来 2 不大于 2,像是能配上,下一帧确认。
- 23确认:2 不大于 2,这是一对有效对,而且此时 i 等于 3 不超过 j 等于 5,下标要求也满足。距离是 j 减 i 等于 2。不过 2 没有超过已经拿到的最大距离 3,最大距离保持不变。接着把 j 右移一格,看能不能让距离更大。
- 24两个指针里,j 已经越过 nums2 的末尾,循环停下来。整趟下来 i 只往右走、j 也只往右走,两个指针各自从头扫到尾,合起来最多走 m 加 n 步。现在把这一路记录到的最大距离揭晓出来。
- 25把最好的那一对摆出来。指针 i 在下标 0,nums1 值是 7;指针 j 在下标 3,nums2 值是 7。7 不超过 7,下标 0 也不超过 3,是一对合法有效对,距离 j 减 i 等于 3。这就是全程能拿到的最大距离。后面 i 挪到 3 之后虽然也能配上,但那时 j 只差 1 到 2,距离都比 3 小。
- 26收个尾。整道题靠两个只往右走的指针:配得上就记距离再把 j 往后拉去争取更大距离,配不上就把 i 往后挪去换个更小的值。nums1 = 7,5,5,2,1 配 nums2 = 9,8,8,7,3,2,最终最大距离是 3。两个指针合起来只扫了一遍,线性时间、常数额外空间,又快又省。
⚠️ 容易写错的地方
✗ 错：只盯着数值 nums1[i] ≤ nums2[j],忘了下标还要 i ≤ j
✓ 对：两个约束一起满足才算有效对:下标 i ≤ j 且数值 nums1[i] ≤ nums2[j]
题目对有效对有两条要求,缺一不可。双指针里真正刷新最大距离的,一定是 i ≤ j 的有效对:当 i 因为配不上而连续右移、暂时跑到 j 前面时,j 减 i 是负数,天然不会成为最大值,并不影响答案;但若换成暴力枚举却漏判 i ≤ j,把 i 大于 j 的非法对也当成正距离算进去,答案就会偏大
✗ 错：把两个数组当成升序来处理,二分方向搞反
✓ 对：认准题目给的是非递增数组,双指针里 j 越往后 nums2 越小
正因为 nums2 非递增,当 nums1[i] 大于 nums2[j] 时,后面更小的 nums2 更配不上,才能果断把 i 右移。若误当升序,这套推进逻辑就不成立,会漏掉或错配下标对
✗ 错：找不到有效对时返回了负数或没初始化的值
✓ 对：最大距离从 0 起步,一个有效对都没有就返回 0
距离 j 减 i 在有效对里最小是 0,题目也规定无有效对时返回 0。若把答案初始化成负数又忘了兜底,像 nums1 全大于 nums2 的情形就会返回一个错误的负数
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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 ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int maxDistance(vector<int>& nums1, vector<int>& nums2) {
int ans = 0;
reverse(nums2.begin(), nums2.end());
for (int i = 0; i < nums1.size(); ++i) {
int j = nums2.size() - (lower_bound(nums2.begin(), nums2.end(), nums1[i]) - nums2.begin()) - 1;
ans = max(ans, j - i);
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int maxDistance(int[] nums1, int[] nums2) {
int ans = 0;
int m = nums1.length, n = nums2.length;
for (int i = 0; i < m; ++i) {
int left = i, right = n - 1;
while (left < right) {
int mid = (left + right + 1) >> 1;
if (nums2[mid] >= nums1[i]) {
left = mid;
} else {
right = mid - 1;
}
}
ans = Math.max(ans, left - 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)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 下标对中的最大距离 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么两个指针都只往右走一遍就够,不会漏掉更优的下标对?+
关键靠两个数组都非递增这个性质。当 nums1[i] 能配上 nums2[j] 时,我们要最大距离,就固定这个 i 让 j 尽量往后,所以右移 j 去争取更大的距离。当 nums1[i] 配不上 nums2[j] 时,因为 nums2 往后只会更小,这个 i 对任何更靠后的 j 都无望,而它和更靠前的 j 在之前已经比过了,所以可以永久放弃它、右移 i。每个 i 只会被放弃一次、每个 j 只会被推进一次,两个指针各自单调前进,既不重复也不遗漏,一遍扫完就是全局最优。
这题的双指针和参考代码里的二分是什么关系,哪个更好?+
两者枚举的是同一批候选。二分版对 nums1 里每个 i,在 nums2 里二分找最靠后那个不小于 nums1[i] 的下标,单次 O(log n)、合计 O(m log n)。双指针版则利用了 j 随 i 单调不减这个规律,把每次二分省成了接着上次位置往前推,合计只要 O(m+n)。答案完全一样,双指针在时间上更优,也不需要反转数组;二分版胜在思路直接、对每个 i 独立求解,写起来不容易错。面试里能说清两者等价、并点出双指针为什么能把 log 去掉,是加分项。
如果把有效对的下标约束从 i ≤ j 去掉,会发生什么?+
如果不要求 i ≤ j,那距离 j 减 i 就可以让 i 尽量小、j 尽量大而不受下标先后限制,题目会退化成另一种问法。本题要求 i ≤ j,所以有效对必须同时满足下标 i ≤ j 和数值 nums1[i] ≤ nums2[j]。这里要澄清一个常见误解:双指针里让我们敢在 nums1[i] 配不上时右移 i 的,并不是 i ≤ j 这个约束,而是 nums2 非递增这个性质,更靠后的 j 只会更小、更配不上当前的 nums1[i],所以这个 i 可以永久丢弃。至于下标约束,它落在结算上:当 i 连续右移暂时跑到 j 前面时,j 减 i 是负数,自然不会被当成最大距离,只有 i ≤ j 的有效对才会真正贡献答案。两点配合,才让线性双指针既正确又高效。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 下标对中的最大距离 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。