300. 最长上升子序列
查看题目中等
数组
高频
解法一：动态规划
时间复杂度：O(n²) | 空间复杂度：O(n) | 推荐使用
动画演示
准备就绪 - 输入数组值（用逗号分隔），然后点击开始
代码实现
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
dp[0] = 1;
int maxans = 1;
for (int i = 1; i < nums.length; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxans = Math.max(maxans, dp[i]);
}
return maxans;
}
}
时间复杂度：O(n²)
空间复杂度：O(n)
动态规划算法求解最长递增子序列：
1. **定义状态**：dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
2. **状态转移方程**：对于每个 i，遍历 j 从 0 到 i-1，如果 nums[i] > nums[j]，则 dp[i] = max(dp[i], dp[j] + 1)
3. **初始状态**：所有 dp[i] 初始化为 1，因为每个元素自身可以构成一个长度为 1 的递增子序列
4. **最终结果**：遍历整个 dp 数组，取最大值即为最长递增子序列的长度
该算法的时间复杂度为 O(n²)，空间复杂度为 O(n)。
解法二：贪心算法+二分查找
时间复杂度：O(n log n) | 空间复杂度：O(n)
动画演示
准备就绪 - 输入数组值（用逗号分隔），然后点击开始
代码实现
class Solution {
public int lengthOfLIS(int[] nums) {
int len = 1, n = nums.length;
if (n == 0) {
return 0;
}
int[] d = new int[n + 1];
d[len] = nums[0];
for (int i = 1; i < n; ++i) {
if (nums[i] > d[len]) {
d[++len] = nums[i];
} else {
int l = 1, r = len, pos = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (d[mid] < nums[i]) {
pos = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
d[pos + 1] = nums[i];
}
}
return len;
}
}
时间复杂度：O(n log n)
空间复杂度：O(n)
贪心算法结合二分查找求解最长递增子序列：
1. **核心思想**：维护一个数组 d，其中 d[i] 表示长度为 i 的递增子序列的最小末尾元素
2. **贪心策略**：对于每个新元素 nums[i]，如果它大于 d 数组的最后一个元素，则直接添加到数组末尾，递增子序列长度加 1；否则，找到 d 数组中第一个大于等于 nums[i] 的位置，并替换该位置的元素
3. **二分查找**：使用二分查找在 O(log n) 时间内找到需要替换的位置
4. **最终结果**：d 数组的长度即为最长递增子序列的长度
该算法的时间复杂度为 O(n log n)，空间复杂度为 O(n)，是求解最长递增子序列的最优算法之一。