LeetCode 300.Longest Increasing Subsequence (最长上升子序列)

痛定思痛。 2022-03-02 16:44 199阅读 0赞

题目描述：

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

**示例:**

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

**说明:**

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

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

解题思路：

![300-1.jpg][]

![300-2.jpg][]

![300-3.jpg][]

AC C++ Solution:

class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            vector<int> res;
            for(int i = 0; i < nums.size(); ++i) {
                auto it = std::lower_bound(res.begin(),res.end(),nums[i]);    //找到插入的位置
                if(it == res.end())        //当前值为最大值，直接构成升序列
                    res.push_back(nums[i]);
                else
                    *it = nums[i];    //替换
            }
            
            return res.size();
        }
    };

[300-1.jpg]: /images/20220302/9ed3a302beec43c2802f50e269290fc5.png
[300-2.jpg]: /images/20220302/cf63ae60e98f46ed918175dd360ddfaf.png
[300-3.jpg]: /images/20220302/af78676db9e84796b896b4154317ddca.png

发表评论取消回复

表情：

评论列表（有 0 条评论，199人围观）

还没有评论，来说两句吧...

相关阅读

相关 300. Longest Increasing Subsequence (Medium)——最长递增子序列

> 前言：本题目为动态规划思想的一道典型例题——最长递增子序列。 > 题目：给定一个无序的整数数组，找到其中最长上升子序列的长度。示例: 输入

小灰灰/ 2023年05月29日 09:20/ 0 赞/ 60 阅读

相关 leetcode.最长上升子序列(longest-increasing-subsequence)

最长上升子序列(longest-increasing-subsequence) [题解][Link 1] 代码一 class Solution {

Myth丶恋晨/ 2022年12月27日 14:29/ 0 赞/ 65 阅读

相关 leetcode 300. Longest Increasing Subsequence | 300. 最长递增子序列（动态规划）

题目 [https://leetcode.com/problems/longest-increasing-subsequence/][https_leetcode.com

雨点打透心脏的1/2处/ 2022年10月12日 14:59/ 0 赞/ 198 阅读

相关 LeetCode300——Longest Increasing Subsequence

LeetCode300——Longest Increasing Subsequence 题意：最长上升子串，LIS问题，经典的动态规划问题。据说有用到二分的方法，这个还没

青旅半醒/ 2022年08月09日 19:30/ 0 赞/ 70 阅读

相关 leetcode 300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

今天药忘吃喽~/ 2022年07月28日 01:20/ 0 赞/ 174 阅读

相关 Leetcode：300. Longest Increasing Subsequence（最大增长序列）

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如

╰+攻爆jí腚メ/ 2022年04月05日 15:48/ 0 赞/ 178 阅读

相关 LeetCode 300.Longest Increasing Subsequence (最长上升子序列)

题目描述：给定一个无序的整数数组，找到其中最长上升子序列的长度。示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释

痛定思痛。/ 2022年03月02日 16:44/ 0 赞/ 200 阅读

相关 LeetCode300最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。示例: 输入: \[10,9,2,5,3,7,101,18\] 输出: 4 解释: 最长的上升子序列是 \[

比眉伴天荒/ 2022年01月05日 04:43/ 0 赞/ 260 阅读

相关【Leetcode】300. Longest Increasing Subsequence（最大上升子序列）

Given an unsorted array of integers, find the length of longest increasing subsequence.

叁歲伎倆/ 2021年12月16日 12:04/ 0 赞/ 238 阅读

相关 LeetCode : 300. Longest Increasing Subsequence 最长上升子序列

试题 Given an unsorted array of integers, find the length of longest increasing subseque

忘是亡心i/ 2021年06月24日 16:11/ 0 赞/ 679 阅读