当前位置：首页 > news >正文

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

news 2026/7/14 22:08:53

【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 <= 10⁵
1 <= nums2.length <= 10⁵
1 <= nums1[i], nums2[j] <= 10⁵
nums1和nums2都是非递增数组

解题方法：双指针

可以枚举j jj，随着j jj的增大，n u m s 2 [ j ] nums2[j]nums2[j]变小，满足n u m s 1 [ i ] ≤ n u m s 2 [ j ] nums1[i]\leq nums2[j]nums1[i]≤nums2[j]的n u m s 1 [ j ] nums1[j]nums1[j]会变小，i ii会增大。

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

时间复杂度O ( l e n ( n u m s 1 ) + l e n ( n u m s 2 ) ) O(len(nums1)+len(nums2))O(len(nums1)+len(nums2))
空间复杂度O ( 1 ) O(1)O(1)

AC代码

C++

/* * @LastEditTime: 2026-04-19 13:38:49 */classSolution{public:intmaxDistance(vector<int>&nums1,vector<int>&nums2){intans=0;for(inti=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);}returnans;}};