Skip to content

Commit 0844084

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.1855. Maximum Distance Between a
Pair of Values
1 parent a169cd2 commit 0844084

File tree

7 files changed

+168
-89
lines changed

7 files changed

+168
-89
lines changed

‎solution/1800-1899/1855.Maximum Distance Between a Pair of Values/README.md

Lines changed: 59 additions & 31 deletions
Original file line numberDiff line numberDiff line change
@@ -65,9 +65,9 @@
6565

6666
<!-- 这里可写通用的实现逻辑 -->
6767

68-
二分法。
68+
二分查找。
6969

70-
遍历数组 A，对于每个数字 `A[i]`，用二分法找到数组 B 中下标最大并且比 `A[i]` 还大的数字即可。
70+
遍历数组 nums1，对于每个数字 `nums1[i]`，用二分法找到数组 nums2 中下标最大并且比 `nums1[i]` 还大的数字即可。
7171

7272
<!-- tabs:start -->
7373

@@ -78,16 +78,16 @@
7878
```python
7979
class Solution:
8080
def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:
81-
res = 0
82-
for i in range(len(nums1)):
83-
l, r = i, len(nums2) - 1
84-
while l <= r:
85-
mid = (l + r) >> 1
86-
if nums2[mid] >= nums1[i]:
87-
res = max(res, mid - i)
88-
l = mid + 1
81+
res, n = 0, len(nums2)
82+
for i, num in enumerate(nums1):
83+
left, right = i, n - 1
84+
while left < right:
85+
mid = (left + right + 1) >> 1
86+
if nums2[mid] >= num:
87+
left = mid
8988
else:
90-
r = mid - 1
89+
right = mid - 1
90+
res = max(res, left - i)
9191
return res
9292
```
9393

@@ -99,17 +99,18 @@ class Solution:
9999
class Solution {
100100
public int maxDistance(int[] nums1, int[] nums2) {
101101
int res = 0;
102-
for (int i = 0; i < nums1.length; ++i) {
103-
int l = i, r = nums2.length - 1;
104-
while (l <= r) {
105-
int mid = (l + r) >>> 1;
102+
int m = nums1.length, n = nums2.length;
103+
for (int i = 0; i < m; ++i) {
104+
int left = i, right = n - 1;
105+
while (left < right) {
106+
int mid = (left + right + 1) >> 1;
106107
if (nums2[mid] >= nums1[i]) {
107-
res = Math.max(res, mid - i);
108-
l = mid + 1;
108+
left = mid;
109109
} else {
110-
r = mid - 1;
110+
right = mid - 1;
111111
}
112112
}
113+
res = Math.max(res, left - i);
113114
}
114115
return res;
115116
}
@@ -123,23 +124,47 @@ class Solution {
123124
public:
124125
int maxDistance(vector<int>& nums1, vector<int>& nums2) {
125126
int res = 0;
126-
for (int i = 0; i < nums1.size(); ++i) {
127-
int l = i, r = nums2.size() - 1;
128-
while (l <= r) {
129-
int mid = (l + r) >> 1;
127+
int m = nums1.size(), n = nums2.size();
128+
for (int i = 0; i < m; ++i) {
129+
int left = i, right = n - 1;
130+
while (left < right) {
131+
int mid = (left + right + 1) >> 1;
130132
if (nums2[mid] >= nums1[i]) {
131-
res = max(res, mid - i);
132-
l = mid + 1;
133+
left = mid;
133134
} else {
134-
r = mid - 1;
135+
right = mid - 1;
135136
}
136137
}
138+
res = max(res, left - i);
137139
}
138140
return res;
139141
}
140142
};
141143
```
142144
145+
### **Go**
146+
147+
```go
148+
func maxDistance(nums1 []int, nums2 []int) int {
149+
res, n := 0, len(nums2)
150+
for i, num := range nums1 {
151+
left, right := i, n-1
152+
for left < right {
153+
mid := (left + right + 1) >> 1
154+
if nums2[mid] >= num {
155+
left = mid
156+
} else {
157+
right = mid - 1
158+
}
159+
}
160+
if res < left-i {
161+
res = left - i
162+
}
163+
}
164+
return res
165+
}
166+
```
167+
143168
### **JavaScript**
144169

145170
```js
@@ -150,17 +175,20 @@ public:
150175
*/
151176
var maxDistance = function(nums1, nums2) {
152177
let res = 0;
153-
for (let i = 0; i < nums1.length; i++) {
154-
let left = 0, right = nums2.length - 1;
155-
while (left <= right) {
156-
mid = (left + right) >> 1;
178+
let m = nums1.length;
179+
let n = nums2.length;
180+
for (let i = 0; i < m; ++i) {
181+
let left = i;
182+
let right = n - 1;
183+
while (left < right) {
184+
const mid = (left + right + 1) >> 1;
157185
if (nums2[mid] >= nums1[i]) {
158-
res = Math.max(res, mid - i);
159-
left = mid + 1;
186+
left = mid;
160187
} else {
161188
right = mid - 1;
162189
}
163190
}
191+
res = Math.max(res, left - i);
164192
}
165193
return res;
166194
};

‎solution/1800-1899/1855.Maximum Distance Between a Pair of Values/README_EN.md

Lines changed: 57 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -67,16 +67,16 @@ The maximum distance is 2 with pair (2,4).
6767
```python
6868
class Solution:
6969
def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:
70-
res = 0
71-
for i in range(len(nums1)):
72-
l, r = i, len(nums2) - 1
73-
while l <= r:
74-
mid = (l + r) >> 1
75-
if nums2[mid] >= nums1[i]:
76-
res = max(res, mid - i)
77-
l = mid + 1
70+
res, n = 0, len(nums2)
71+
for i, num in enumerate(nums1):
72+
left, right = i, n - 1
73+
while left < right:
74+
mid = (left + right + 1) >> 1
75+
if nums2[mid] >= num:
76+
left = mid
7877
else:
79-
r = mid - 1
78+
right = mid - 1
79+
res = max(res, left - i)
8080
return res
8181
```
8282

@@ -86,17 +86,18 @@ class Solution:
8686
class Solution {
8787
public int maxDistance(int[] nums1, int[] nums2) {
8888
int res = 0;
89-
for (int i = 0; i < nums1.length; ++i) {
90-
int l = i, r = nums2.length - 1;
91-
while (l <= r) {
92-
int mid = (l + r) >>> 1;
89+
int m = nums1.length, n = nums2.length;
90+
for (int i = 0; i < m; ++i) {
91+
int left = i, right = n - 1;
92+
while (left < right) {
93+
int mid = (left + right + 1) >> 1;
9394
if (nums2[mid] >= nums1[i]) {
94-
res = Math.max(res, mid - i);
95-
l = mid + 1;
95+
left = mid;
9696
} else {
97-
r = mid - 1;
97+
right = mid - 1;
9898
}
9999
}
100+
res = Math.max(res, left - i);
100101
}
101102
return res;
102103
}
@@ -110,23 +111,47 @@ class Solution {
110111
public:
111112
int maxDistance(vector<int>& nums1, vector<int>& nums2) {
112113
int res = 0;
113-
for (int i = 0; i < nums1.size(); ++i) {
114-
int l = i, r = nums2.size() - 1;
115-
while (l <= r) {
116-
int mid = (l + r) >> 1;
114+
int m = nums1.size(), n = nums2.size();
115+
for (int i = 0; i < m; ++i) {
116+
int left = i, right = n - 1;
117+
while (left < right) {
118+
int mid = (left + right + 1) >> 1;
117119
if (nums2[mid] >= nums1[i]) {
118-
res = max(res, mid - i);
119-
l = mid + 1;
120+
left = mid;
120121
} else {
121-
r = mid - 1;
122+
right = mid - 1;
122123
}
123124
}
125+
res = max(res, left - i);
124126
}
125127
return res;
126128
}
127129
};
128130
```
129131
132+
### **Go**
133+
134+
```go
135+
func maxDistance(nums1 []int, nums2 []int) int {
136+
res, n := 0, len(nums2)
137+
for i, num := range nums1 {
138+
left, right := i, n-1
139+
for left < right {
140+
mid := (left + right + 1) >> 1
141+
if nums2[mid] >= num {
142+
left = mid
143+
} else {
144+
right = mid - 1
145+
}
146+
}
147+
if res < left-i {
148+
res = left - i
149+
}
150+
}
151+
return res
152+
}
153+
```
154+
130155
### **JavaScript**
131156

132157
```js
@@ -137,17 +162,20 @@ public:
137162
*/
138163
var maxDistance = function(nums1, nums2) {
139164
let res = 0;
140-
for (let i = 0; i < nums1.length; i++) {
141-
let left = 0, right = nums2.length - 1;
142-
while (left <= right) {
143-
mid = (left + right) >> 1;
165+
let m = nums1.length;
166+
let n = nums2.length;
167+
for (let i = 0; i < m; ++i) {
168+
let left = i;
169+
let right = n - 1;
170+
while (left < right) {
171+
const mid = (left + right + 1) >> 1;
144172
if (nums2[mid] >= nums1[i]) {
145-
res = Math.max(res, mid - i);
146-
left = mid + 1;
173+
left = mid;
147174
} else {
148175
right = mid - 1;
149176
}
150177
}
178+
res = Math.max(res, left - i);
151179
}
152180
return res;
153181
};

‎solution/1800-1899/1855.Maximum Distance Between a Pair of Values/Solution.cpp

Lines changed: 8 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -2,17 +2,18 @@ class Solution {
22
public:
33
int maxDistance(vector<int>& nums1, vector<int>& nums2) {
44
int res = 0;
5-
for (int i = 0; i < nums1.size(); ++i) {
6-
int l = i, r = nums2.size() - 1;
7-
while (l <= r) {
8-
int mid = (l + r) >> 1;
5+
int m = nums1.size(), n = nums2.size();
6+
for (int i = 0; i < m; ++i) {
7+
int left = i, right = n - 1;
8+
while (left < right) {
9+
int mid = (left + right + 1) >> 1;
910
if (nums2[mid] >= nums1[i]) {
10-
res = max(res, mid - i);
11-
l = mid + 1;
11+
left = mid;
1212
} else {
13-
r = mid - 1;
13+
right = mid - 1;
1414
}
1515
}
16+
res = max(res, left - i);
1617
}
1718
return res;
1819
}

‎solution/1800-1899/1855.Maximum Distance Between a Pair of Values/Solution.go

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
func maxDistance(nums1 []int, nums2 []int) int {
2+
res, n := 0, len(nums2)
3+
for i, num := range nums1 {
4+
left, right := i, n-1
5+
for left < right {
6+
mid := (left + right + 1) >> 1
7+
if nums2[mid] >= num {
8+
left = mid
9+
} else {
10+
right = mid - 1
11+
}
12+
}
13+
if res < left-i {
14+
res = left - i
15+
}
16+
}
17+
return res
18+
}

‎solution/1800-1899/1855.Maximum Distance Between a Pair of Values/Solution.java

Lines changed: 8 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,17 +1,18 @@
11
class Solution {
22
public int maxDistance(int[] nums1, int[] nums2) {
33
int res = 0;
4-
for (int i = 0; i < nums1.length; ++i) {
5-
int l = i, r = nums2.length - 1;
6-
while (l <= r) {
7-
int mid = (l + r) >>> 1;
4+
int m = nums1.length, n = nums2.length;
5+
for (int i = 0; i < m; ++i) {
6+
int left = i, right = n - 1;
7+
while (left < right) {
8+
int mid = (left + right + 1) >> 1;
89
if (nums2[mid] >= nums1[i]) {
9-
res = Math.max(res, mid - i);
10-
l = mid + 1;
10+
left = mid;
1111
} else {
12-
r = mid - 1;
12+
right = mid - 1;
1313
}
1414
}
15+
res = Math.max(res, left - i);
1516
}
1617
return res;
1718
}

‎solution/1800-1899/1855.Maximum Distance Between a Pair of Values/Solution.js

Lines changed: 9 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -5,17 +5,20 @@
55
*/
66
var maxDistance = function(nums1, nums2) {
77
let res = 0;
8-
for (let i = 0; i < nums1.length; i++) {
9-
let left = 0, right = nums2.length - 1;
10-
while (left <= right) {
11-
mid = (left + right) >> 1;
8+
let m = nums1.length;
9+
let n = nums2.length;
10+
for (let i = 0; i < m; ++i) {
11+
let left = i;
12+
let right = n - 1;
13+
while (left < right) {
14+
const mid = (left + right + 1) >> 1;
1215
if (nums2[mid] >= nums1[i]) {
13-
res = Math.max(res, mid - i);
14-
left = mid + 1;
16+
left = mid;
1517
} else {
1618
right = mid - 1;
1719
}
1820
}
21+
res = Math.max(res, left - i);
1922
}
2023
return res;
2124
};

0 commit comments

Comments
 (0)