[LeetCode] 300、最长上升子序列

题目描述

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例：

输入:[10,9,2,5,3,7,101,18]输出:4解释:最长的上升子序列是[2,3,7,101]，它的长度是4。

说明:

• 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
• 你算法的时间复杂度应该为 O(n2) 。

进阶: 你能将算法的时间复杂度降低到O ( n l o g n ) O(n log n)O(nlogn)吗?

解题思路

这是一个子序列问题，子序列问题基本都可以归化为“动态规划”问题。

• 动态规划（四要素：状态表示、初始化、状态转移方程、返回值）

  • 使用数组cell保存每步子问题的最优解，cell[i]代表以nums[i]为结尾的最长上升子序列长度
  • 求解cell[i]时，向前遍历找出比i元素小的元素j，状态转移方程为：cell[i] = max（cell[i], cell[j] + 1)。（0 <= j < i && cell[j] < cell[i]）
  • 初始化：cell[0] = 1（一定要把整个数组全部初始化为1）
  • 迭代过程中不断更新最大值，返回值为迭代过程中的最大值。两次遍历数组，时间复杂度O ( n 2 ) O(n^2)O(n2)。

• 动态规划 + 二分：进阶要求时间复杂度要求O ( n l o g n ) O(nlogn)O(nlogn)，立马想到二分。这个思路比较巧妙，很具小巧思。

  • 新建数组cell，用于保存最长上升子序列（保存的是序列，不是状态表示了）。对原序列进行遍历，将每位元素二分插入cell中。
  • 如果cell中元素都比它小，将它插到最后。
  • 否则，用它覆盖掉大于等于它的元素中最小的那个。

  总之，思想就是让cell中存储比较小的元素。这样，cell未必是真实的最长上升子序列，但长度是对的。

参考代码

动态规划（也要会）

classSolution{public:intlengthOfLIS(vector<int>&nums){intlength=nums.size();if(length==1){return1;}intres=1;// 结果默认值为1vector<int>dp(length,1);for(inti=1;i<length;i++){for(intj=0;j<i;j++){if(nums[j]<nums[i]){dp[i]=max(dp[i],dp[j]+1);}}res=max(res,dp[i]);}returnres;}};

按照模板写的二分（推荐）

• 核心思想

  • 维护一个数组 res，始终保持严格递增，且 res 的长度就是当前最长上升子序列的长度。
  • 关键点：res 不一定是真实的最长子序列，但它的长度一定是对的。

• 为什么替换不会破坏长度的正确性？

  • 替换操作只是把 res[idx] 换成更小的值
  • 既没有让 res 变长（长度不变）
  • 也没有让 res 变短（长度不变）
  • 只是让 res[idx] 变得更小，为后续元素创造更大的上升空间

一句话总结：res 中的元素不一定是真实子序列，但通过贪心地用更小的值替换，保证了 res 始终是最优状态，使得后续元素有最大的上升空间，因此 res.size() 始终等于当前最长上升子序列的长度。

classSolution{public:intlengthOfLIS(vector<int>&nums){intleft=0,right=nums.size()-1;vector<int>res;for(inti=0;i<nums.size();i++){if(res.empty()||nums[i]>res.back()){res.push_back(nums[i]);continue;}intidx=binarySearchIdx(res,nums[i]);// 注意：这里传的数组是resres[idx]=nums[i];}returnres.size();}// 首先要明确我们的目的是要找第一个“大于等于k”的元素的下标intbinarySearchIdx(vector<int>&nums,inttarget){intleft=0,right=nums.size()-1;while(left<right){intmid=left+(right-left)/2;if(nums[mid]<target){left=mid+1;}else{right=mid;}}returnleft;}};

进阶

要求返回最长的上升子序列

核心思路：在 DP 的同时，用一个 path 数组记录每个位置的最优前驱节点，最后从终点往前回溯。

参考代码（基于上述dp的方法，改动几点而已）

classSolution{public:vector<int>lengthOfLIS(vector<int>&nums){intlength=nums.size();if(length==1){return{nums[0]};}intres=1;intendPos=0;// 新增：记录最长子序列的结束位置vector<int>dp(length,1);// dp[i] 表示以 nums[i] 结尾的最长上升子序列长度vector<int>path(length,-1);// 新增：path[i] 记录每个位置 i 的前驱节点索引（默认-1）for(inti=1;i<length;i++){for(intj=0;j<i;j++){if(nums[j]<nums[i]){if(dp[j]+1>dp[i]){// 原来的 max 改成 if，方便同时更新 pathdp[i]=dp[j]+1;path[i]=j;// 新增：更新前驱}}}if(dp[i]>res){res=dp[i];endPos=i;// 新增：更新结束位置}}// 新增：从 endPos 沿 path 回溯还原子序列vector<int>result;for(inti=endPos;i!=-1;i=path[i]){// 注意这里的 "i = path[i]" 操作，很骚result.push_back(nums[i]);}reverse(result.begin(),result.end());returnresult;}};