1855.下标对中的最大距离：双指针

【LetMeFly】1855.下标对中的最大距离：双指针

力扣题目链接：https://leetcode.cn/problems/maximum-distance-between-a-pair-of-values/

给你两个 非递增 的整数数组 nums1​​​​​​ 和 nums2​​​​​​ ，数组下标均 从 0 开始 计数。

下标对 (i, j) 中 0 <= i < nums1.length 且 0 <= j < nums2.length 。如果该下标对同时满足 i <= j 且 nums1[i] <= nums2[j] ，则称之为 有效 下标对，该下标对的 距离 为 j - i​​ 。​​

返回所有 有效 下标对 (i, j) 中的 最大距离 。如果不存在有效下标对，返回 0 。

一个数组 arr ，如果每个 1 <= i < arr.length 均有 arr[i-1] >= arr[i] 成立，那么该数组是一个 非递增 数组。

 

示例 1：

输入：nums1 = [55,30,5,4,2], nums2 = [100,20,10,10,5]
输出：2
解释：有效下标对是 (0,0), (2,2), (2,3), (2,4), (3,3), (3,4) 和 (4,4) 。
最大距离是 2 ，对应下标对 (2,4) 。

示例 2：

输入：nums1 = [2,2,2], nums2 = [10,10,1]
输出：1
解释：有效下标对是 (0,0), (0,1) 和 (1,1) 。
最大距离是 1 ，对应下标对 (0,1) 。

示例 3：

输入：nums1 = [30,29,19,5], nums2 = [25,25,25,25,25]
输出：2
解释：有效下标对是 (2,2), (2,3), (2,4), (3,3) 和 (3,4) 。
最大距离是 2 ，对应下标对 (2,4) 。

 

提示：

• 1 <= nums1.length <= 105
• 1 <= nums2.length <= 105
• 1 <= nums1[i], nums2[j] <= 105
• nums1 和 nums2 都是 非递增 数组

解题方法：双指针

可以枚举$j$，随着$j$的增大，$nums2[j]$变小，满足$nums1[i]\leq nums2[j]$的$nums1[j]$会变小，$i$会增大。

使用双指针，在枚举$j$的时候，不断增大$i$并保持$nums1[i]\leq nums2[j]$。如果$i$超出数组范围，则说明$nums1$中最小的元素仍然大于$nums2[j]$，退出。

• 时间复杂度$O(len(nums1)+len(nums2))$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @LastEditTime: 2026-04-19 13:38:49
 */
class Solution {
public:
    int maxDistance(vector<int>& nums1, vector<int>& nums2) {
        int ans = 0;
        for (int i = 0, j = 0, n = nums1.size(), m = nums2.size(); j < m; j++) {
            while (i < n && nums1[i] > nums2[j]) {
                i++;
            }
            if (i == n) {
                break;
            }
            ans = max(ans, j - i);
        }
        return ans;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源