1855. 下标对中的最大距离 - 力扣（LeetCode）
1855. 下标对中的最大距离 - 给你两个 非递增 的整数数组 nums1 和 nums2 ，数组下标均 从 0 开始 计数。 下标对 (i, j) 中 0 <= i < nums1.length 且 0 <= j < nums2.length 。如果该下标对同时满足 i <= j 且 nums1[i] <= nums2[j] ，则称之为 有效 下标对，该下标对的 距离 为 j - i 。 返回所有 有效 下标对 (i, j) 中的 最大距离 。如果不存在有效下标对，返回 0...
思路
注意到两个序列都已经有序，这题可以考虑双指针或者二分查找做法。
咱觉得双指针的思路很自然，假设 i 指定 nums1 的元素，j 指定 nums2 的元素：
- 如果
nums1[i] > nums2[j]，则后移i，直至i移动到尽头或者满足nums1[i] <= nums2[j]。
（因为在nums1[i] > nums2[j]时，就算j更大，因为序列是非递增的，必然还是会有nums1[i] > nums2[j]） - 若满足第一条，就可以后移一次
j，更新结果。
（因为距离是下标距离，我希望能在保持nums1[i] <= nums2[j]的同时j-i尽量大）
理清这两步后写起来就很容易了。
代码
class Solution {
public:
int maxDistance(vector<int>& nums1, vector<int>& nums2) {
// 注意 nums1 和 nums2 都是有序的
// 因此这题能用上双指针
// 注意距离是下标差，因此 nums1 中每个数 X 尽量要在 nums2 中找到最后一个 Y>=X
int p1=0,p2=0;
int n1=nums1.size(),n2=nums2.size();
int res=0;
while(p1<n1&&p2<n2){
while(p1<n1&&nums2[p2]<nums1[p1]){
// 不满足 nums2[j] >= nums1[i] 时前移 i
p1++;
}
res=max(res,p2-p1);
p2++;
}
return res;
}
};
接着再复习一些题 （点击了解更多详细信息）
1 个帖子 - 1 位参与者
来源: linux.do查看原文