好用心 做网站送女友县建设局 协会网站

LeetCode 300. 最长递增子序列

题目描述

给定一个未排序的整数数组 nums，找出其中最长递增子序列的长度。

要求：

• 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
• 例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列

示例 1:

输入: nums = [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长递增子序列为 [2,3,7,101]，因此长度为 4。

示例 2:

输入: nums = [0,1,0,3,2,3]
输出: 4
解释: 最长递增子序列为 [0,1,2,3] 或 [0,1,3] 或 [0,3,2,3]，长度均为 4。

示例 3:

输入: nums = [7,7,7,7,7]
输出: 1
解释: 最长递增子序列为 [7]，长度为 1。

Java 实现代码

class Solution {public int lengthOfLIS(int[] nums) {if (nums.length == 0)return 0;int[] dp = new int[nums.length];int maxLength = 1;Arrays.fill(dp, 1);for (int i = 1; i < nums.length; i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) {dp[i] = Math.max(dp[i], dp[j] + 1);}}maxLength = Math.max(maxLength, dp[i]);}return maxLength;}
}

解题思路

1. 边界条件处理：

   • 如果输入数组 nums 为空，直接返回长度为 0。

2. 初始化：

   • 创建一个长度与 nums 相同的数组 dp，用于存储到每个位置为止的最长递增子序列的长度。
   • 使用 Arrays.fill(dp, 1) 将 dp 数组的所有元素初始化为 1，因为每个元素自身可以看作是一个长度为 1 的递增子序列。

3. 动态规划过程：

   • 外层循环遍历数组 nums 的每个元素，从第二个元素开始（索引 1）。
   • 内层循环遍历当前元素之前的所有元素（索引 0 到 i-1）。
   • 如果当前元素 nums[i] 大于之前的某个元素 nums[j]，则说明可以通过添加 nums[i] 来扩展以 nums[j] 结尾的递增子序列。
   • 更新 dp[i] 为 dp[j] + 1，表示以 nums[i] 结尾的递增子序列的长度。
   • 同时，更新 maxLength 为 dp[i] 和当前 maxLength 的最大值，以记录遍历过程中找到的最长递增子序列的长度。

4. 返回结果：

   • 遍历完成后，maxLength 存储的就是整个数组的最长递增子序列的长度。

复杂度分析

• 时间复杂度：O(n^2)，其中 n 是数组 nums 的长度。这是因为有两层循环，外层循环 n 次，内层循环在最坏情况下也是 n 次。
• 空间复杂度：O(n)，需要一个大小为 n 的数组 dp 来存储中间结果。

注：题目来源leetcode网站