LeetCode 1855. 下标对中的最大距离【数组,二分；同向双指针】中等

memcpy0

415人浏览 · 2021-05-14 01:17:21

memcpy0 · 2021-05-14 01:17:21 发布

本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，本系列的终止日期可能是永远。在这一系列刷题文章中，我不仅会讲解多种解题思路及其优化，还会用多种编程语言实现题解，涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件，我还建立了相关的仓库：https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中，你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等，还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解，还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动，欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

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

解法1 二分

由于两个数组有序，因此对于每个 0 <= i < nums1.length ，都可以在 i <= j < nums2.length 范围内寻找最后一个大于等于 nums1[i] 的 nums2[j] ，即为相对于 nums1[i] 的最远有效下标对 (i, j) 。这种做法的时间复杂度为 $O(n\log n)$ 。

手写如下，由于习惯了 lower_bound, upper_bound API，所以这里将寻找最后一个 >= nums1[i] 的 nums2[j] 的位置，转换为寻找第一个 < nums1[i] 的 nums2[j] 的位置 lo ，lo - 1 就是目标位置：

class Solution {
public:
    int maxDistance(vector<int>& nums1, vector<int>& nums2) {
        int ans = 0, m = nums1.size(), n = nums2.size();
        for (int i = 0; i < m; ++i) { //找到最后一个>=nums1[i]的nums2[j]
            int lo = i, hi = n; //找到第一个<nums1[i]的nums2[j]
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;
                if (nums2[mid] < nums1[i]) hi = mid;
                else lo = mid + 1;
            }
            if (lo == i) continue; //不存在i<=j且nums2[j]>=nums1[i]的j
            if (lo - 1 - i > ans) ans = lo - 1 - i;
        }
        return ans;
    }
};

写成寻找最后一个 >= nums1[i] 的 nums2[j] 的位置 也不难，只是不太符合我的编程习惯：

class Solution {
public:
    int maxDistance(vector<int>& nums1, vector<int>& nums2) {
        int ans = 0, m = nums1.size(), n = nums2.size();
        for (int i = 1; i <= m; ++i) { // 找到最后一个>=nums1[i]的nums2[j]
            int lo = i - 1, hi = n; // 位置的解的范围应该在[i-1,n]
            while (lo < hi) {
                int mid = (lo + hi + 1) / 2;
                if (nums2[mid - 1] >= nums1[i - 1]) lo = mid;
                else hi = mid - 1;
            } 
            if (lo < i) continue; // 不存在i<=j且nums2[j]>=nums1[i]的j
            if (lo - i > ans) ans = lo - i;
        }
        return ans;
    }
};

STL提供的 upper_bound ，有如下情况：

lower_bound(v.begin(), v.end(), target, less<int>()); 默认选项，在非降序序列中寻找第一个大于等于 target 的值的位置；
upper_bound(v.begin(), v.end(), target, less<int>()); 默认选项，在非降序序列中寻找第一个大于 target 的值的位置；
lower_bound(v.begin(), v.end(), target, greater<int>()); 在非升序序列中寻找第一个小于等于 target 的值的位置；
upper_bound(v.begin(), v.end(), target, greater<int>()); 在非升序序列中寻找第一个小于 target 的值的位置。

class Solution {
public:
    int maxDistance(vector<int>& nums1, vector<int>& nums2) {
        int ans = 0, m = nums1.size(), n = nums2.size();
        for (int i = 0; i < m; ++i) { //找到最后一个>=nums1[i]的nums2[j]
            auto it = upper_bound(nums2.begin() + i, nums2.end(), nums1[i], greater<int>()); //找到第一个<nums1[i]的nums2[j]
            int j = it - nums2.begin() - 1; 
            if (j < i) continue; //不存在i<=j且nums2[j]>=nums1[i]的j
            if (j - i > ans) ans = j - i;
        }
        return ans;
    }
};

解法2 双指针（最优）

枚举 $j$ ，随着 $j$ 的变大， $nums_2[j]$ 变小，满足要求的最小的 $i$ 随之变大。所以可用同向双指针做。

如果 $j$ 变大后，发现 $nums_1[i] > nums_2[j]$ ，那么增大 $i$ ，直到 $i = n$ 或 $nums_1[i] \le nums_2[j]$ 为止，然后用 $j - i$ 更新答案的最大值（初始化为 $0$ ）。

无需担心 $j - i < 0$ ，这不会影响答案。

class Solution {
    public int maxDistance(int[] nums1, int[] nums2) {
        int ans = 0;
        int i = 0;
        for (int j = 0; j < nums2.length; j++) {
            while (i < nums1.length && nums1[i] > nums2[j]) { // 不满足条件
                i++;
            }
            if (i == nums1.length) {
                break;
            }
            ans = Math.max(ans, j - i);
        }
        return ans;
    }
}

class Solution {
public:
    int maxDistance(vector<int>& nums1, vector<int>& nums2) {
        int ans = 0;
        int i = 0;
        for (int j = 0; j < nums2.size(); j++) {
            while (i < nums1.size() && nums1[i] > nums2[j]) {
                i++;
            }
            if (i == nums1.size()) {
                break;
            }
            ans = max(ans, j - i);
        }
        return ans;
    }
};
// 特殊写法，找到最大的距离
class Solution {
public:
    int maxDistance(vector<int>& nums1, vector<int>& nums2) {
        int ans = 0, m = nums1.size(), n = nums2.size();
        for (int i = 0; i < m; ++i) 
            while (i + ans < n && nums2[i + ans] >= nums1[i]) ++ans;
        return ans == 0 ? 0 : ans - 1;
    }
};

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

impl Solution {
    pub fn max_distance(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
        let mut ans = 0;
        let mut i = 0;
        for (j, y) in nums2.into_iter().enumerate() {
            while i < nums1.len() && nums1[i] > y {
                i += 1;
            }
            if i == nums1.len() {
                break;
            }
            ans = ans.max(j as i32 - i as i32);
        }
        ans
    }
}

func maxDistance(nums1, nums2 []int) (ans int) {
	i := 0
	for j, y := range nums2 {
		for i < len(nums1) && nums1[i] > y {
			i++
		}
		if i == len(nums1) {
			break
		}
		ans = max(ans, j-i)
	}
	return
}

var maxDistance = function(nums1, nums2) {
    let ans = 0;
    let i = 0;
    for (let j = 0; j < nums2.length; j++) {
        while (i < nums1.length && nums1[i] > nums2[j]) {
            i++;
        }
        if (i === nums1.length) {
            break;
        }
        ans = Math.max(ans, j - i);
    }
    return ans;
};

int maxDistance(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int ans = 0;
    int i = 0;
    for (int j = 0; j < nums2Size; j++) {
        int y = nums2[j];
        while (i < nums1Size && nums1[i] > y) {
            i++;
        }
        if (i == nums1Size) {
            break;
        }
        ans = MAX(ans, j - i);
    }
    return ans;
}