Solutions CS101

Appearance

M1855.下标对中的最大距离 ​

two pointers, binary search, 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 <= 10^5
  • 1 <= nums2.length <= 10^5
  • 1 <= nums1[i], nums2[j] <= 10^5
  • nums1 和 nums2 都是 非递增 数组

这个问题可以通过 双指针 法来解决，时间复杂度为 O(n+m)。

解题思路

  1. 题目特点：

    • nums1 和 nums2 都是 非递增 的（即单调不增，从大到小）。
    • 有效条件：i≤j 且 nums1[i] <= nums2[j]。
    • 目标：最大化 j−i。

  2. 双指针逻辑：

    • 我们使用两个指针 i 和 j 分别指向 nums1 和 nums2 的起始位置。
    • 在每一轮循环中，我们检查 nums1[i] 是否小于等于 nums2[j]：
      • 如果 nums1[i] <= nums2[j]：说明这是一个潜在的有效对。由于我们需要寻找最大距离，而 nums2 是非递增的，后面可能还有满足条件且更远的 j。因此，我们记录当前距离 j - i，并尝试让 j 向右移动（j += 1）。
      • 如果 nums1[i] > nums2[j]：说明当前的 nums2[j] 太小了。因为 nums2 是非递增的，j 再往后只会更小，更不可能满足 nums1[i] <= nums2[j]。此时唯一的办法是增大 nums2[j] 的相对值，也就是减小 nums1[i]，所以我们将 i 向右移动（i += 1）。
    • 在这个过程中，如果 i > j，j - i 会变成负数，不会更新最大值，指针 j 会在后续步骤中追上或超过 i。

代码实现

python
class Solution:
    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:
        i = 0
        j = 0
        max_dist = 0
        n1, n2 = len(nums1), len(nums2)
        
        while i < n1 and j < n2:
            # 如果满足有效条件
            if nums1[i] <= nums2[j]:
                # 更新最大值 (这里隐含了 i <= j 的判断，
                # 因为如果 i > j，j - i 是负数，不会更新 max_dist)
                if j - i > max_dist:
                    max_dist = j - i
                # 尝试向右移动 j 以获得更大的距离
                j += 1
            else:
                # nums1[i] 太大了，向右移动 i 以减小 nums1[i]
                i += 1
                
        return max_dist

复杂度分析

  • 时间复杂度：O(n+m)，其中 n 和 m 分别是 nums1 和 nums2 的长度。每个指针最多遍历数组一次。
  • 空间复杂度：O(1)，只使用了常数级别的辅助变量。

为什么不用二分查找？

虽然这题也可以对 nums1 中的每个元素在 nums2 中进行二分查找（因为 nums2 是有序的），时间复杂度为 O(nlog⁡m)。但在两个数组均有序的情况下，双指针法能达到线性时间复杂度，效率更高。