下标对中的最大距离
难度:
标签:
题目描述
代码结果
运行时间: 70 ms, 内存: 31.0 MB
/*
* 思路:
* 1. 使用IntStream遍历nums1和nums2中的索引。
* 2. 对于每一个有效的下标对(i, j),计算距离并找到最大值。
*/
import java.util.stream.IntStream;
public int maxDistanceStream(int[] nums1, int[] nums2) {
return IntStream.range(0, nums1.length)
.flatMap(i -> IntStream.range(i, nums2.length)
.filter(j -> nums1[i] <= nums2[j])
.map(j -> j - i))
.max()
.orElse(0);
}
解释
方法:
此题解采用双指针方式来寻找最大距离。由于数组nums1和nums2都是非递增的,我们可以利用这一特性优化搜索过程。算法从数组的开始处同时遍历nums1和nums2。使用两个指针i和j分别指向nums1和nums2的当前元素。如果nums1[i] > nums2[j],即当前nums1的元素大于nums2的元素,不满足nums1[i] <= nums2[j]的条件,因此需要将指针i向右移动,试图找到一个更小的数使条件得到满足。同时,无论是否移动i,都将j向右移动。这样,即使i不变,j的增加也可能增加满足条件的下标对的距离。整个过程持续到任一数组遍历完毕。最后,因为j在最后一次循环中会多增加一次,所以计算最大距离时需要用(j - i - 1)来确保不超出数组边界,并与0取最大值来处理不存在有效下标对的情况。
时间复杂度:
O(n + m)
空间复杂度:
O(1)
代码细节讲解
🦆
在算法实现中,为什么在判断`nums1[i] > nums2[j]`时仅移动指针i,而指针j在每次循环中都会移动?
▷🦆
算法中提到的最后一次循环j会多增加一次,这种处理方式是否可能导致跳过一些潜在的有效下标对?
▷🦆
如果在某次比较中`nums1[i]`恰好等于`nums2[j]`,这时是否有更优的策略来处理指针的移动,以提高寻找最大距离的效率?
▷🦆
算法中提到,返回结果时使用了`max(j - i - 1, 0)`,请解释为什么要从j减去i后再减1,这里的减1操作具体是为了什么?
▷