算法日记40：最长上升子序列LIS（单调栈优化）n*log^n

一、题目：

二、题解：

1、通过观察我们发现，传统的$O(n^2)$的线性DP做法无法通过题目的全部样例，且我们需要一种$O(n\ast lo{g}^n)$的做法

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[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(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;
}