LeetCode 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 1051 nums2.length 1051 nums1[i], nums2[j] 105nums1和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(vectorintnums1,vectorintnums2){intans0;for(inti0,j0,nnums1.size(),mnums2.size();jm;j){while(innums1[i]nums2[j]){i;}if(in){break;}ansmax(ans,j-i);}returnans;}};同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~千篇源码题解已开源