300. 最长递增子序列
Ⅰ、动态规划
-
代表前
个元素，以第
- 每次 遍历一个
，更新
public class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
int[] dp = new int[n];
dp[0] = 1;
int maxLen = 1;
for (int i = 1; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i])
dp[i] = Math.max(dp[i], dp[j] + 1);
}
maxLen = Math.max(maxLen, dp[i]);
}
return maxLen;
}
}
Ⅱ、二分查找 + 贪心
- 贪心思想：
- 顺序遍历一遍
，为了达到最长的升序序列，尽可能取最小的值到
中
-
- 在升序
需要存放的位置，二分范围
-
，可以直接插入到
在最后，此时“扩容”
res++ -
二分找到最靠近前面位置的可插入位置，然后覆盖插入，不需要扩容
-
- 顺序遍历一遍
- 准备一个
，
即作为结果，同时也是二分查找的右边界
- 最终的
res
public int lengthOfLIS(int[] nums) {
int[] tails = new int[nums.length];
int res = 0;
for (int num : nums) {
int l = 0, r = res; // 确定好 tails 区间范围
while (l < r) {
int mid = l + ((r - l) >>> 1);
if (num > tails[mid])
l = mid + 1;
else
r = mid;
}
tails[l] = num; // 当前值替换二分找到的 l 位置
if (res == r) res++; // 需要“扩容”
}
return res;
}
