Leetcode 1855. Maximum Distance Between a Pair of Values

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

1. Description

Maximum Distance Between a Pair of Values

2. Solution

解析:Version 1,由于两个数组都是非增数组,因此保证了数值的大小关系,如果i<=j,此时比较nums1[i] <= nums2[j],如果符合,则计算距离distance,并与已有距离比较取较大值,在i<=jnums1[i] > nums2[j]的情况下,此时应该移动i,如果i>j,则移动j,由于保证了大小关系,因此只要遍历完一个数组即可。Version 2是对Version 1的进一步优化。

  • Version 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:
distance = 0
i = 0
j = 0
while i < len(nums1) and j < len(nums2):
if i <= j:
if nums1[i] <= nums2[j]:
distance = max(distance, j - i)
j += 1
else:
i += 1
else:
j += 1
return distance
  • Version 2
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:
distance = 0
i = 0
j = 0
while i < len(nums1) and j < len(nums2):
if nums1[i] > nums2[j]:
i += 1
else:
distance = max(distance, j - i)
j += 1
return distance

Reference

  1. https://leetcode.com/problems/maximum-distance-between-a-pair-of-values/
如果有收获,可以请我喝杯咖啡!