/
300.java
63 lines (62 loc) · 1.97 KB
/
300.java
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
__________________________________________________________________________________________________
sample 0 ms submission
class Solution {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length + 1];
int size = 0;
dp[0] = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > dp[size]) {
dp[++size] = nums[i];
} else {
int idx = binarySearch(dp, size, nums[i]);
dp[idx] = nums[i];
}
}
return size;
}
private int binarySearch(int[] a, int size, int target) {
int lo = 0;
int hi = size;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] >= target) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
}
__________________________________________________________________________________________________
sample 33980 kb submission
class Solution {
public int lengthOfLIS(int[] nums) {
int[] minLast = new int[nums.length + 1];
Arrays.fill(minLast, Integer.MAX_VALUE);
minLast[0] = Integer.MIN_VALUE;
for(int i = 0; i < nums.length; i++) {
int index = binarySearch(minLast, nums[i]);
minLast[index] = nums[i];
}
for(int i = minLast.length - 1; i >= 1; i--) {
if(minLast[i] != Integer.MAX_VALUE)
return i;
}
return 0;
}
private int binarySearch(int[] minLast, int target) {
int left = 0, right = minLast.length - 1;
while(left + 1 < right) {
int mid = (right - left) / 2 + left;
if(minLast[mid] < target) {
left = mid;
} else {
right = mid;
}
}
return right;
}
}
__________________________________________________________________________________________________