下标对中的最大距离 图解题解

两个非递增数组里，要挑距离最大的哪种下标对

给两个非递增数组 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)）。

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 ans

C++

#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;
    }
}