leetcode
leetcode 1651 ~ 1700
下标对中的最大距离

下标对中的最大距离

难度:

标签:

题目描述

代码结果

运行时间: 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在每次循环中都会移动?
在算法中,目的是找到符合条件`nums1[i] <= nums2[j]`的最大下标距离。当`nums1[i] > nums2[j]`时,因为nums1是非递增的,所以移动指针i到更高的下标,可能会找到一个更小或等于的值满足条件。而移动j的目的是尽可能增加下标距离,在每次迭代中不断测试新的下标对是否可以增加最大距离。因此,无论i是否移动,j都会向右移动以探索更大的下标差。
🦆
算法中提到的最后一次循环j会多增加一次,这种处理方式是否可能导致跳过一些潜在的有效下标对?
实际上,最后一次循环中j的增加是因为循环条件结束时j还会自增一次,但这并不导致跳过任何有效下标对。因为一旦循环终止,意味着已经没有更多的nums2的元素来与nums1中的任何未测试的元素形成新的下标对,因此不会错过任何有效的下标对。
🦆
如果在某次比较中`nums1[i]`恰好等于`nums2[j]`,这时是否有更优的策略来处理指针的移动,以提高寻找最大距离的效率?
当`nums1[i]`恰好等于`nums2[j]`时,已满足条件`nums1[i] <= nums2[j]`,此时i位置是有效的。因为nums1是非递增的,i后面的数只会更小或相等,因此可以继续尝试增加j以探索更大的距离,而无需移动i。在这种情况下,移动j是最有效的策略,因为它可以帮助我们尝试找到更大的下标差。
🦆
算法中提到,返回结果时使用了`max(j - i - 1, 0)`,请解释为什么要从j减去i后再减1,这里的减1操作具体是为了什么?
在最后一次循环结束时,j会因循环的条件自增一次,因此它会超出最后一个真实比较的下标。因此,要计算实际的最大距离,我们需要从j减去i后再减1,以确保反映的是最后一个有效比较中i和j的实际距离。这个减1操作是为了调整因循环自增导致的j的超出。使用`max`函数则是为了处理不存在有效下标对的情况,确保返回的结果不会是负数。

相关问题