Medium

题目描述

给你两个 非递增 的 0 索引整数数组 nums1 和 nums2。

下标对 (i, j)，其中 0 <= i < nums1.length 且 0 <= j < nums2.length，如果满足 i <= j 且 nums1[i] <= nums2[j] ，该下标对就是 有效 的。该下标对的 距离 为 j - i。

返回所有 有效 下标对 (i, j) 中的 最大距离。如果不存在有效下标对，返回 0。

一个数组 arr ，如果每个 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,4) 的距离 2。

示例 2：

输入：nums1 = [2,2,2], nums2 = [10,10,1]
输出：1
解释：有效的下标对是 (0,0), (0,1), 和 (1,1)。
最大距离是下标对 (0,1) 的距离 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,4) 的距离 2。

提示：

  • 1 <= nums1.length, nums2.length <= 10^5
  • 1 <= nums1[i], nums2[j] <= 10^5
  • nums1 和 nums2 都是非递增数组

解题思路

解题思路

这道题需要找到满足条件的下标对 (i, j) 的最大距离，其中条件为 i <= j 且 nums1[i] <= nums2[j]。

方法一：双指针（推荐）

利用两个数组都是非递增的特性。对于 nums1[i]，如果我们已经找到了满足条件的最远位置 j，那么对于 nums1[i+1]（由于非递增，nums1[i+1] <= nums1[i]），满足条件的最远位置至少也是 j，可能更远。

算法步骤：

  1. 使用两个指针 i 和 j 分别指向两个数组
  2. 如果满足 i <= j 且 nums1[i] <= nums2[j]，记录距离并尝试增大 j
  3. 否则增大 i
  4. 重复直到遍历完成

方法二：二分查找

对于每个 nums1[i]，使用二分查找在 nums2 中找到满足 nums2[j] >= nums1[i] 的最大下标 j，然后检查是否满足 i <= j。

双指针方法更直观且时间复杂度更优，因此推荐使用。

代码实现

class Solution {
public:
    int maxDistance(vector<int>& nums1, vector<int>& nums2) {
        int maxDist = 0;
        int i = 0, j = 0;
        
        while (i < nums1.size() && j < nums2.size()) {
            if (i <= j && nums1[i] <= nums2[j]) {
                maxDist = max(maxDist, j - i);
                j++;
            } else {
                i++;
            }
        }
        
        return maxDist;
    }
};

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

public class Solution {
    public int MaxDistance(int[] nums1, int[] nums2) {
        int maxDist = 0;
        int i = 0, j = 0;
        
        while (i < nums1.Length && j < nums2.Length) {
            if (i <= j && nums1[i] <= nums2[j]) {
                maxDist = Math.Max(maxDist, j - i);
                j++;
            } else {
                i++;
            }
        }
        
        return maxDist;
    }
}

var maxDistance = function(nums1, nums2) {
    let maxDist = 0;
    let i = 0, j = 0;
    
    while (i < nums1.length && j < nums2.length) {
        if (i <= j && nums1[i] <= nums2[j]) {
            maxDist = Math.max(maxDist, j - i);
            j++;
        } else {
            i++;
        }
    }
    
    return maxDist;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度
双指针O(m + n)O(1)
二分查找O(m log n)O(1)

其中 m 和 n 分别是 nums1 和 nums2 的长度。

相关题目