算法日记40:最长上升子序列LIS(单调栈优化)n*log^n
一、题目:
二、题解:
1、通过观察我们发现,传统的 O ( n 2 ) O(n^2) O(n2)的线性DP做法无法通过题目的全部样例,且我们需要一种 O ( n ∗ l o g n ) O(n*log^n) O(n∗logn)的做法
2、因此我们考虑可以优化找有某个数作为其倒数第二个数的遍历做法,我们考虑可以使用单调栈优化
1)接下来,我们来分析优化单调栈的具体操作
- 假设我们现在有这样的一个数组
- 首先,我们遍历到
a[1]
,此时我们发现栈为空(stk.empty()
),因此以a[1]
为最后一位的最长上升子序列是1
- 接着,我们遍历到
a[2]
,此时我们发现栈内没有一个元素比它大,只有一个元素比它小(a[1]),因此将其入栈,因此以a[2]
为最后一位的最长上升子序列是stk[1]+1
- 重点:接着,我们遍历到
a[3]
,此时我们发现栈内有一个元素比它大(a[2]),因此我们可以将stk[2]取代(因为往后选择了a[2]
一定不如选择了a[5]
的),因此将其入栈,因此以a[3]
为最后一位的最长上升子序列是stk[1]+1=2
- 遍历到
a[4]
,此时我们发现栈内没有一个元素比它大,有两个元素比它小(a[1],a[3]),因此将其入栈,因此以a[4]
为最后一位的最长上升子序列是stk[2]+1=3
- 遍历到
a[5]
,此时我们发现栈内没有一个元素比它大,有三个元素比它小(a[1],a[3],a[4]),因此将其入栈,因此以a[4]
为最后一位的最长上升子序列是stk[3]+1=4
- 遍历到
a[6]
,此时我们发现栈内元素(a[4],a[5])比它大,有两个个元素比它小(a[1],a[3]),因此将取代a[4](最后一个<=a[6]的位置+1),因此以a[6]
为最后一位的最长上升子序列是stk[2]+1=3
- 转变为
−
>
->
−>
2)因此我们可以发现,一个数a[x]可以取代stk[ a [ i ] a[i] a[i]]的条件为:
- 更长:子序列长度(a[x]>a[i])
- 更矮: a[x]<a[i],即x的权重更小
3、代码分块解析:
1) 全局变量与常量定义
typedef long long ll;
const int N=2e5+7;
int a[N];
int dp[N]; //表示[i]个数的最长上升子序列
int stk[N], top = 0; //维护一个单调栈
-
typedef long long ll;
定义ll
为长整型的别名,便于书写和理解。 -
const int N = 2e5+7;
定义了一个常量N
,作为数组的最大长度。这里设置为 200,000 多一点,保证在处理较大规模数据时不会越界。 -
int a[N];
用于存储输入的序列。注意:数组下标从 1 开始读入数据(见下面的循环)。 -
int stk[N], top = 0;
使用数组stk
和变量top
来维护一个单调栈。- 这里的“单调栈”实际上指的是“尾部数组”,它用来记录对于不同长度的上升子序列,其末尾可能的最小值。
- 变量
top
表示栈中(或尾部数组中)已有元素的数量,也即当前最长上升子序列的长度。
2)solve()
函数解析
void solve()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
int res = 0;
for (int i = 1; i <= n; i++) // 遍历序列
{
// 找到当前栈中第一个大于 a[i] 的位置
// 这个位置即为“最后一个不大于 a[i] 的数”的下一个位置,
// 对应着以 a[i] 作为结尾能够构成的最长上升子序列的长度
//最后一个<=a[i]+1下标 == 第一个>a[i]的下标
int pos = upper_bound(stk + 1, stk + 1 + top, a[i]) - stk;
// 如果 pos 恰好等于 top+1,说明 a[i] 比栈中所有元素都大,可以延长子序列
if (pos == top + 1)
top++;
// //值赋值给stk[pos]用来下一次的比较
stk[pos] = a[i];
// 更新最长上升子序列的长度
res = max(res, pos);
}
cout << res << '\n';
}
3.1 遍历每个元素构造上升子序列
-
初始化
res = 0;
用于保存最后计算出的最长上升子序列(LIS)的长度。 -
主循环
for (int i = 1; i <= n; i++)
对序列中每个数a[i]
进行处理,考虑它作为上升子序列的“最后一个数”。 -
int pos = upper_bound(stk+1, stk+1+top, a[i]) - stk;
这里用到 STL 中的upper_bound
算法:- 搜索范围:
stk+1
到stk+1+top
(因为数组下标从 1 开始使用),即当前维护的“尾部数组”。 - 搜索目的:找出第一个严格大于
a[i]
的元素下标。这样,pos-1
位置保存的元素是最后一个不大于a[i]
的值,意味着将a[i]
放在位置pos
后,能够构成一个更长的上升子序列。 - 注意:返回的
pos
是一个整数下标,通过减去stk
得到实际的位置。
- 搜索范围:
-
判断是否需要扩展“尾部数组”
if (pos == top + 1) top++;
- 如果
pos
等于top+1
,说明a[i]
比栈中所有元素都大,无法在已有序列中找到合适的位置替换,因此需要扩展序列长度(即top
加 1)。
- 如果
-
更新“尾部数组”
stk[pos] = a[i];
- 无论是扩展子序列还是在中间位置更新,都将
a[i]
存入stk[pos]
。 - 这样保证:对于长度为
pos
的上升子序列,记录的尾部元素尽可能小,这对于后续扩展子序列非常关键。
- 无论是扩展子序列还是在中间位置更新,都将
-
更新最长上升子序列的结果
res = max(res, pos);
- 每次更新
res
为目前找到的最大子序列长度。
- 每次更新
3.3 输出结果
cout << res << '\n';
将计算出的最长上升子序列长度输出。
5. 算法核心思想
-
算法思路
- 使用贪心思想和二分查找(
upper_bound
)来维护一个“尾部数组”(或称“单调栈”)。 - 对于每个元素
a[i]
,在当前“尾部数组”中找到第一个大于a[i]
的位置,并更新该位置。 - 如果
a[i]
大于所有当前尾部值,则扩展序列长度。 - 这种方法的时间复杂度为 O ( n l o g n ) O(n log n) O(nlogn),比传统的动态规划方法更高效。
- 使用贪心思想和二分查找(
-
关键点
- 维护尾部数组:对于长度为
k
的上升子序列,尽量保存一个更小的尾部值有助于后续更容易构造更长的子序列。 - 二分查找:利用
upper_bound
快速查找适合a[i]
插入的位置。
- 维护尾部数组:对于长度为
三、完整代码实现:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+7;
int a[N];
int dp[N]; //表示[i]个数的最长上升子序列
int stk[N],top=0; //维护一个单调栈
void solve()
{
int n;cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int res=0;
for(int i=1;i<=n;i++) //遍历选择最后一个数
{
//找此时第一个>a[i]的下标,
//也正是其能够组成的最长上升子序列长度:最后一个<=a[i]的序列长度+1
int pos=upper_bound(stk+1,stk+1+top,a[i])-stk;
if(pos == top+1) top++; //表明此时a[i]比栈中所有元素都大,栈长度+1
stk[pos]=a[i]; //值赋值给stk[pos]用来下一次的比较
res=max(res,pos);
}
cout<<res<<'\n';
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _=1;
while(_--) solve();
return 0;
}