题解 | #最长递增子序列#(一个数组记录查找最长上升子序列的过程,后面较小值可能覆盖结果,需要记录值并回溯)

最长递增子序列

http://www.nowcoder.com/practice/9cf027bf54714ad889d4f30ff0ae5481

转载大佬&自己增加解释

class Solution {
public:
    vector<int> LIS(vector<int>&amp; arr) {
        vector<int> res; // 贪心下,用res数组存储最长上升子序列
        vector<int> maxLen;// maxLen[i]:加入arr[i]元素的最大长度。
        if (arr.size() &lt; 1) return res;
        res.emplace_back(arr[0]);  // emplace_back(val)作用同push_back,效率更高
        maxLen.emplace_back(1);
        for (int i = 1; i &lt; arr.size(); ++i) { 
            if (arr[i] &gt; res.back()) {
                res.emplace_back(arr[i]);  // 大于res中保存上升子序列的最后一个元素。 
                maxLen.emplace_back(res.size()); 
                //res记录且maxLen记录加入该元素时最大上升长度。 
            } else { 
                // 它的作用是返回有序数组begin..end中第一个大于等于val的元素的迭代器
                res[pos] = arr[i]; // 将arr[i]元素加入满足第一个大于它的元素处,此处贪心
        //不影响后续判断,在求最长上升子序列中,中间元素可以替换,记录后续情况。arr[i]替换res[pos]的原因
                maxLen.emplace_back(pos+1); // 记录以arr[i]结尾的最长长度。
            }
        }
        // 第二步:填充最长递增子序列,贪心时后面添加元素可能覆盖正确的升上子序列
        for (int i = arr.size()-1, j = res.size(); j &gt; 0; --i) {
            if (maxLen[i] == j) { 
         // 当以arr[i]结尾的最长长度是满足当前元素前最大上升子序列长度时,
         // res中的位置 替换成 arr[i] ,这样从前往后执行最后会得到序列最小的最长上升子序列。
                res[--j] = arr[i]; //j:是从1到res.size(),减1才对应在res中的位置
            }
        }
        return res;
    }
};

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
1 收藏 评论
分享

全站热榜

正在热议