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
26
27
28
29
30
31
32
33
34
35
36
37
| class Solution {
int[] a, b;
Map<Integer, Integer>[] cache;
public int makeArrayIncreasing(int[] a, int[] b) {
this.a = a;
this.b = b;
Arrays.sort(b);
int n = a.length;
cache = new HashMap[n];
Arrays.setAll(cache, e -> new HashMap<>());
int ans = dfs(n - 1, Integer.MAX_VALUE);
return ans < Integer.MAX_VALUE / 2 ? ans : -1;
}
private int dfs(int i, int pre) {
if (i < 0) return 0;
if (cache[i].containsKey(pre)) return cache[i].get(pre);
int res = a[i] < pre ? dfs(i - 1, a[i]) : Integer.MAX_VALUE / 2;
int k = lowerBound(b, pre) - 1;
if (k >= 0) res = Math.min(res, dfs(i - 1, b[k]) + 1);
cache[i].put(pre, res);
return res;
}
private int lowerBound(int[] nums, int target) {
int left = -1, right = nums.length;
while (left + 1 < right) {
int mid = (left + right) >> 1;
if (nums[mid] < target) left = mid;
else right = mid;
}
return right;
}
}
|
wechat
