C++二分查找算法的应用：最长递增子序列

涉及知识点

二分查找 单调映射

源码下载

点击下载源码

题目

给你一个整数数组 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

示例 3：

输入：nums = [7,7,7,7,7,7,7]

输出：1

参数范围：

1 <= nums.length <= 2500

-104 <= nums[i] <=104

暴力解法

分析

m_vRet[i]，记录以nums[i]结尾的最长严格递增系列。计算m_vRet[i]的方法：nums[j] < nums[i]中最大m_vRet[j]+1。如果不存在合法的j，则m_vRet[i]等于1。

下表以{1,2,6,5,4,5}

i

m_vRet[0,i)，加粗表示nums[j]<nums[i]

m_vRet[i]

0

1

1

1

2{1,2}

2

1 2

3{1,2,6}

3

1 2 3

3{1,2,5}

4

1 2 3 3

3{1,2,4}

5

1 2 3 3 3

4{1,2,4,5}

两层循环，分别枚举i和j，故总时间复杂度是O(n2)。

代码

class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
                   m_c = nums.size();
                   m_vRet.resize(m_c);
for (int i = 0; i < m_c; i++)
                   {
int iPreLen = 0;
for (int j = 0; j < i; j++)
                            {
if (nums[j] >= nums[i])
                                     {
continue;
                                     }
                                     iPreLen = max(iPreLen, m_vRet[j]);
                            }
                            m_vRet[i] = iPreLen + 1;
                   }
return *std::max_element(m_vRet.begin(), m_vRet.end());
         }
vector<int> m_vRet;
int m_c;
};

有序映射

分析

如果nums[j1] > nums[j2]，且m_vRet[j1] <= m_vRet[j2]，那么j1被j2淘汰。以nums[j]为key，m_vRet[j]为值，创建有序映射。key和value都是升序。

下表以{1,2,6,5,4,5,5}为列来说明,加粗表示新增加，删除线表示删除。

{1,1}

{1,1}，{2,2}

{1,1}，{2,2}，{6,3}

{1,1},{2,2},{5,3},{6,3}

{1,1},{2,2},{4,3},{5,3}

{1,1},{2,2},{4,3},{5,4}

{1,1},{2,2},{4,3},{5,4}

代码

class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
                   m_c = nums.size();
                   m_vRet.resize(m_c);
                   std::map<int, int> mValueLen = { {-1000 * 1000,0} };
for (int i = 0; i < m_c; i++)
                   {
//计算以nums[i]结尾的最长长度
auto it = mValueLen.lower_bound(nums[i]);
const int iLen = std::prev(it)->second + 1;
                            m_vRet[i] = iLen;
//如果nums[j] >= nums[j]，且长度小于等于删除
auto ij = it;
for (; (ij != mValueLen.end()) && (ij->second <= iLen); ++ij);
                            mValueLen.erase(it, ij);
//如果nums[i]存在，说明旧值比当前值大，不能处理
if (!mValueLen.count(nums[i]))
                            {
                                     mValueLen[nums[i]] = iLen;
                            }
                   }
return *std::max_element(m_vRet.begin(), m_vRet.end());
         }
vector<int> m_vRet;
int m_c;
};

运行验证环境

Win10 VS2022 Ck++17 或win7 VS2019 C++17

每天都补充正能量

好好学习，天天向上。

事无终始，无务多业。

是故置本不安者，无务丰末。

相关下载

如果你时间宝贵，只想看精华，请到下载频道下载《闻缺陷则喜算法册》doc版