Temp
数组d相当于记录了所有 长度为 index的 子数组。
But the tricky part is it only records the tail for each of them.
See the example below.
The reason you do this, is that, it can keep you array d increasing.
Why?
e.g. for n1 & n2. if n1 < n2, then, 以n1 结尾的升序子数组的长度， 一定小于 以n2结尾的升序子数组长度。
Which means:
- d数组一定是升序的， 但是前提条件是 d数组中， 对于 各个长度一样的 子数组， 一定记录 最小的tail值。
重点在于理解 d数组实际的含义， 以及， 为什么d数组一定是递增的。
进而 it’s easy to realize the Binary Search Thing.
More about why 对于一样len的子数组， 一定将tails中元素记录更小的值。
e.g. [10, 3, 8]
当遍历到 index = 1， 即nums[i] = 3 时， 此时d[1] = 10; 而 元素3的长度也是1， 但是由于3<10, 所以以10 结尾的 子数组必定不会长过以3小的子数组。
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
| class Solution {
private int len;
private int[] tails;
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0)
return -1;
tails = new int[nums.length + 1];
tails[1] = nums[0];
this.len = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > tails[len]) {
tails[++len] = nums[i];
continue;
}
int index = getIndex(nums[i]);
tails[index] = nums[i];
}
return len;
}
private int getIndex(int target) {
int left = 1;
int right = this.len;
while (left < right) {
int mid = left + (right - left) / 2;
if (tails[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}
|