1855-下标对中的最大距离

给你两个 非递增 的整数数组 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 都是 非递增 数组

方法一：双指针

提示 1

考虑遍历下标对中的某一个下标，并寻找此时所有有效坐标对中距离最大的另一个下标。暴力遍历另一个下标显然不满足时间复杂度要求，此时是否存在一些可以优化寻找过程的性质？

思路与算法

不失一般性，我们遍历 nums}_2 中的下标 j，同时寻找此时符合要求的 nums}_1 中最小的下标 i。

假设下标 j 对应的最小下标为 i，当 j 变为 j + 1 时，由于 nums}_2 非递增，即 nums}_2[j] \ge \textit{nums}_2[j+1]，那么 nums}_1 中可取元素的上界不会增加。同时由于 nums}_1 也非递增，因此 j + 1 对应的最小下标 i’ 一定满足 i’ \ge i。

那么我们就可以在遍历 j 的同时维护对应的 i，并用 res 来维护下标对 (i, j) 的最大距离。我们将 res 初值置为 0，这样即使存在 nums}_1[i] \le \textit{nums}_2[j] 但 i > j 这种不符合要求的情况，由于此时距离为负因而不会对结果产生影响（不存在时也返回 0）。

另外，在维护最大距离的时候要注意下标 i 的合法性，即 i < n_1，其中 n_1 为 nums}_1 的长度。

代码

[sol1-C++]

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

[sol1-Python3]

class Solution:
    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:
        n1, n2 = len(nums1), len(nums2)
        i = 0
        res = 0
        for j in range(n2):
            while i < n1 and nums1[i] > nums2[j]:
                i += 1
            if i < n1:
                res = max(res, j - i)
        return res

复杂度分析

• 时间复杂度：O(n_1 + n_2)，其中 n_1, n_2 分别为 nums}_1 与 nums}_2 的长度。在双指针寻找最大值的过程中，我们最多会遍历两个数组各一次。

• 空间复杂度：O(1)，我们使用了常数个变量进行遍历。