LeetCode 300. 最长递增子序列 (Longest Increasing Subsequence) Java实现题目给定一个整数数组 nums找到其中最长严格递增子序列的长度。子序列不要求连续。示例输入: nums [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长递增子序列是 [2,3,7,101] 或 [2,3,7,18]长度为 4。解法一动态规划 O(n²)思路定义 dp[i] 为以 nums[i] 结尾的最长递增子序列长度。初始化 dp[i] 1。对于每个 i遍历 j i若 nums[j] nums[i]则 dp[i] max(dp[i], dp[j] 1)。最终答案是 dp 数组的最大值。classSolution{publicintlengthOfLIS(int[]nums){if(numsnull||nums.length0)return0;intnnums.length;int[]dpnewint[n];intmaxLen1;for(inti0;in;i){dp[i]1;for(intj0;ji;j){if(nums[j]nums[i]){dp[i]Math.max(dp[i],dp[j]1);}}maxLenMath.max(maxLen,dp[i]);}returnmaxLen;}}复杂度时间 O(n²)空间 O(n)。解法二贪心 二分 O(n log n)推荐思路维护一个数组 tails其中 tails[i] 表示长度为 i1 的递增子序列的最小结尾元素。遍历每个数字 num· 在 tails 中用二分查找找到第一个 大于等于 num 的位置因为要求严格递增。· 若找到用 num 替换该位置若没找到即 num 比所有元素都大则追加到末尾。· 最终 tails 的长度就是最长递增子序列的长度。classSolution{publicintlengthOfLIS(int[]nums){if(numsnull||nums.length0)return0;int[]tailsnewint[nums.length];intsize0;// tails 的有效长度for(intnum:nums){// 二分查找第一个 num 的位置intleft0,rightsize;while(leftright){intmidleft(right-left)/2;if(tails[mid]num){leftmid1;}else{rightmid;}}tails[left]num;if(leftsize)size;// 追加到末尾}returnsize;}}复杂度时间 O(n log n)空间 O(n)。关键点说明严格递增二分时找第一个 num 的位置替换。若题目改为非严格递增允许相等则找第一个 num 的位置条件改为 tails[mid] num。tails 数组本身并不一定是最终的最长递增子序列但它的大小一定等于 LIS 的长度。例如 nums [10,9,2,5,3,7,101,18]tails 变化过程10 - [10] 9 - [9] 2 - [2] 5 - [2,5] 3 - [2,3] 7 - [2,3,7]101 - [2,3,7,101]18 - [2,3,7,18]最终长度 43. **重复元素**如 [2,2]第一个 2 放入 tails[0]第二个 2 替换 tails[0]长度仍为 1符合严格递增。 --- ## 测试用例 java public static void main(String[] args) { Solution sol new Solution(); System.out.println(sol.lengthOfLIS(new int[]{10,9,2,5,3,7,101,18})); // 4 System.out.println(sol.lengthOfLIS(new int[]{0,1,0,3,2,3})); // 4 System.out.println(sol.lengthOfLIS(new int[]{7,7,7,7,7})); // 1 }两种解法均可 AC面试中推荐掌握 O(n log n) 的贪心二分法。 
长河君 · 2026/10/11 7:28:09 · 阅读 1.2k DeepSeek LeetCode 300. 最长递增子序列 Java实现
LeetCode 300. 最长递增子序列 (Longest Increasing Subsequence) Java实现题目给定一个整数数组 nums找到其中最长严格递增子序列的长度。子序列不要求连续。示例输入: nums [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长递增子序列是 [2,3,7,101] 或 [2,3,7,18]长度为 4。解法一动态规划 O(n²)思路定义 dp[i] 为以 nums[i] 结尾的最长递增子序列长度。初始化 dp[i] 1。对于每个 i遍历 j i若 nums[j] nums[i]则 dp[i] max(dp[i], dp[j] 1)。最终答案是 dp 数组的最大值。classSolution{publicintlengthOfLIS(int[]nums){if(numsnull||nums.length0)return0;intnnums.length;int[]dpnewint[n];intmaxLen1;for(inti0;in;i){dp[i]1;for(intj0;ji;j){if(nums[j]nums[i]){dp[i]Math.max(dp[i],dp[j]1);}}maxLenMath.max(maxLen,dp[i]);}returnmaxLen;}}复杂度时间 O(n²)空间 O(n)。解法二贪心 二分 O(n log n)推荐思路维护一个数组 tails其中 tails[i] 表示长度为 i1 的递增子序列的最小结尾元素。遍历每个数字 num· 在 tails 中用二分查找找到第一个 大于等于 num 的位置因为要求严格递增。· 若找到用 num 替换该位置若没找到即 num 比所有元素都大则追加到末尾。· 最终 tails 的长度就是最长递增子序列的长度。classSolution{publicintlengthOfLIS(int[]nums){if(numsnull||nums.length0)return0;int[]tailsnewint[nums.length];intsize0;// tails 的有效长度for(intnum:nums){// 二分查找第一个 num 的位置intleft0,rightsize;while(leftright){intmidleft(right-left)/2;if(tails[mid]num){leftmid1;}else{rightmid;}}tails[left]num;if(leftsize)size;// 追加到末尾}returnsize;}}复杂度时间 O(n log n)空间 O(n)。关键点说明严格递增二分时找第一个 num 的位置替换。若题目改为非严格递增允许相等则找第一个 num 的位置条件改为 tails[mid] num。tails 数组本身并不一定是最终的最长递增子序列但它的大小一定等于 LIS 的长度。例如 nums [10,9,2,5,3,7,101,18]tails 变化过程10 - [10] 9 - [9] 2 - [2] 5 - [2,5] 3 - [2,3] 7 - [2,3,7]101 - [2,3,7,101]18 - [2,3,7,18]最终长度 43. **重复元素**如 [2,2]第一个 2 放入 tails[0]第二个 2 替换 tails[0]长度仍为 1符合严格递增。 --- ## 测试用例 java public static void main(String[] args) { Solution sol new Solution(); System.out.println(sol.lengthOfLIS(new int[]{10,9,2,5,3,7,101,18})); // 4 System.out.println(sol.lengthOfLIS(new int[]{0,1,0,3,2,3})); // 4 System.out.println(sol.lengthOfLIS(new int[]{7,7,7,7,7})); // 1 }两种解法均可 AC面试中推荐掌握 O(n log n) 的贪心二分法。