简介：最长递增子序列：给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。动态规划,patience game,LIS,二维LIS
2 动态规划设计
2.1 最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
1
2
3
|
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
|
示例 2：
1
2
|
输入：nums = [0,1,0,3,2,3]
输出：4
|
示例 3：
1
2
|
输入：nums = [7,7,7,7,7,7,7]
输出：1
|
提示：
- 1 <= nums.length <= 2500
- -104 <= nums[i] <= 104
解法一
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
|
class Solution {
public int lengthOfLIS(int[] nums) {
//边界条件： 1 <= nums.length <= 2500
int n = nums.length;
// if(n == 1) return 1;
//dp解法：
//1.定义dp数组的含义，并初始化：dp[i]表示：到i位置为止的最长递增子序列的长度
int[] dp = new int[n];
Arrays.fill(dp, 1);
//2.定义 base case：到第0个位置，只有一个元素，所以最长递增子序列的长度为1，即dp[0] = 1
// dp[0] = 1;
//3.找到状态转移方程：dp[i] = max(dp[n] + 1, dp[i])，其中n = i-1, i-2, ..., 0
for(int i = 0; i < n; i++) {
for(int j = i - 1; j >= 0; j--) {
if(nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
int ans = -1;
for(int i = 0; i < n; i++) {
ans = Math.max(ans, dp[i]);
}
return ans;
}
}
|
解法二
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
|
class Solution {
public int lengthOfLIS(int[] nums) {
//边界条件： 1 <= nums.length <= 2500
int n = nums.length;
if(n == 1) return 1;
//patience sort
int[] top = new int[n]; //牌堆最上方的元素
int piles = 0; //牌堆总数
for(int i = 0; i < n; i++) {
int poker = nums[i];
int pos = getPos(top, piles, poker);
if(pos == piles) {
//将poker放到一个新的牌堆
top[piles++] = poker;
} else {
//将poker放到第pos个牌堆上方
top[pos] = poker;
}
}
return piles;
}
public int getPos(int[] top, int piles, int poker) {
//二分搜索插入，把poker放到合适的位置
int left = 0, right = piles - 1;
while(left <= right) {
int mid = (right - left) / 2 + left;
if(top[mid] < poker) {
left = mid + 1;
} else if(top[mid] > poker) {
right = mid - 1;
} else if(top[mid] == poker) {
//收缩右侧边界
right = mid - 1;
}
}
return left;
}
}
|
2.2 二维递增子序列：信封嵌套问题
给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。
示例 1：
1
2
3
|
输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
|
示例 2：
1
2
|
输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1
|
提示：
- 1 <= envelopes.length <= 105
- envelopes[i].length == 2
- 1 <= wi, hi <= 105
解题思路：先对信封宽度w进行升序排列，如果遇到w相同的情况，则按照高度h降序排列。之后把所有的h作为一个数组，在这个数组上计算出的LIS（最长递增子序列）的长度就是答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public int maxEnvelopes(int[][] envelopes) {
int n = envelopes.length;
Arrays.sort(envelopes, new Comparator<int[]>() {
// 按宽度升序排列，如果宽度一样，则按高度降序排列
public int compare(int[] a, int[] b) {
return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0];
}
});
//对高度数组求解LIS
int[] height = new int[n];
for(int i = 0; i < n; i++) {
height[i] = envelopes[i][1];
}
return lengthOfLIS(height);
}
public int lengthOfLIS(int[] nums) {
//LIS的实现参考2.1
}
}
|
总结
二分查找
找出第一个大于等于自身元素的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
public int getPos(int[] top, int piles, int poker) {
//二分搜索插入，把poker放到合适的位置
int left = 0, right = piles - 1;
while(left <= right) {
int mid = (right - left) / 2 + left;
if(top[mid] < poker) {
left = mid + 1;
} else if(top[mid] > poker) {
right = mid - 1;
} else if(top[mid] == poker) {
//收缩右侧边界
right = mid - 1;
}
}
return left;
}
|
数组排序
nums是一个二维数组，[[5,4],[6,4],[6,7],[2,3]]
排序规则：优先第一维度升序，其次第二维度降序
1
2
3
4
5
|
Arrays.sort(nums, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0];
}
});
|
