下标对中的最大距离

标签: 数组 双指针 二分查找

难度: Medium

给你两个 非递增 的整数数组 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 <= 105
  • 1 <= nums2.length <= 105
  • 1 <= nums1[i], nums2[j] <= 105
  • nums1 和 nums2 都是 非递增 数组

Submission

运行时间: 70 ms

内存: 31.0 MB

from bisect import bisect_left as bisect

class Solution:
    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:
        len1,len2 = len(nums1),len(nums2)
        i,j = 0,0
        while i < len1 and j < len2:
            if nums1[i] > nums2[j]:
                i += 1
            j += 1
        return max(j-i-1, 0)

Explain

此题解采用双指针方式来寻找最大距离。由于数组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)

from bisect import bisect_left as bisect

class Solution:
    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:
        len1, len2 = len(nums1), len(nums2)  # 获取两个数组的长度
        i, j = 0, 0  # 初始化两个指针
        while i < len1 and j < len2:  # 当两个指针都未遍历完各自数组时继续循环
            if nums1[i] > nums2[j]:  # 如果当前nums1的元素大于nums2的元素
                i += 1  # 移动指针i以寻找可能的更小的元素
            j += 1  # 无论是否移动i，都将j向右移动以尝试增加距离
        return max(j - i - 1, 0)  # 计算最大距离，考虑边界情况和不存在有效下标对的情况

Explore

在算法中，目的是找到符合条件`nums1[i] <= nums2[j]`的最大下标距离。当`nums1[i] > nums2[j]`时，因为nums1是非递增的，所以移动指针i到更高的下标，可能会找到一个更小或等于的值满足条件。而移动j的目的是尽可能增加下标距离，在每次迭代中不断测试新的下标对是否可以增加最大距离。因此，无论i是否移动，j都会向右移动以探索更大的下标差。

实际上，最后一次循环中j的增加是因为循环条件结束时j还会自增一次，但这并不导致跳过任何有效下标对。因为一旦循环终止，意味着已经没有更多的nums2的元素来与nums1中的任何未测试的元素形成新的下标对，因此不会错过任何有效的下标对。

当`nums1[i]`恰好等于`nums2[j]`时，已满足条件`nums1[i] <= nums2[j]`，此时i位置是有效的。因为nums1是非递增的，i后面的数只会更小或相等，因此可以继续尝试增加j以探索更大的距离，而无需移动i。在这种情况下，移动j是最有效的策略，因为它可以帮助我们尝试找到更大的下标差。

在最后一次循环结束时，j会因循环的条件自增一次，因此它会超出最后一个真实比较的下标。因此，要计算实际的最大距离，我们需要从j减去i后再减1，以确保反映的是最后一个有效比较中i和j的实际距离。这个减1操作是为了调整因循环自增导致的j的超出。使用`max`函数则是为了处理不存在有效下标对的情况，确保返回的结果不会是负数。