F_JustWei's Studio.

5751. 下标对中的最大距离

leetcode
字数统计: 473阅读时长: 2 min
2021/05/09 Share

5751. 下标对中的最大距离

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

1
2
3
4
输入：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：

1
2
3
4
输入：nums1 = [2,2,2], nums2 = [10,10,1]
输出：1
解释：有效下标对是 (0,0), (0,1) 和 (1,1) 。
最大距离是 1 ，对应下标对 (0,1) 。

示例 3：

1
2
3
4
输入：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) 。

示例 4：

1
2
3
输入：nums1 = [5,4], nums2 = [3,2]
输出：0
解释：不存在有效下标对，所以返回 0 。

提示：

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

思路：

双指针。

C++代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int maxDistance(vector<int>& nums1, vector<int>& nums2) {
        int ans = 0;
        int i = 0;
        int j = 0;

        while (i < nums1.size() && j < nums2.size()) {
            if (i <= j && nums1[i] <= nums2[j]) {
                ans = max(ans, j - i);
                j++;
            }
            else {
                if (nums1[i] > nums2[j]) {
                    i++;
                }
                else {
                    j++;
                }
            }
        }

        return ans;
    }
};

原文作者：F_JustWei

原文链接：http://139.196.79.90/2021/05/09/5751-%E4%B8%8B%E6%A0%87%E5%AF%B9%E4%B8%AD%E7%9A%84%E6%9C%80%E5%A4%A7%E8%B7%9D%E7%A6%BB/

发表日期：May 9th 2021, 2:02:29 pm

更新日期：May 9th 2021, 2:04:10 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 5751. 下标对中的最大距离
    1. 1.0.1. 示例 1：
    2. 1.0.2. 示例 2：
    3. 1.0.3. 示例 3：
    4. 1.0.4. 示例 4：
    5. 1.0.5. 提示：
    6. 1.0.6. 思路：
    7. 1.0.7. C++代码：
Total : 130
2021
2019
leetcode 动态规划 字符串 树 数据结构 C++ STL algorithm 容器 操作系统 软考 Java PTA 计算机网络 UML 迭代器 C JSON 信息安全 模板 多媒体， 软考 数据库 软件工程 排序 Spring 人机交互