当前位置: 首页 > article >正文

算法日记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(nlogn)的做法

在这里插入图片描述

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+1stk+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;
}

http://www.kler.cn/a/584286.html

相关文章:

  • DeepSeek一键生成可视化看板
  • 3.12-1 html讲解
  • QQuick-Binding的介绍
  • e2studio开发RA4L1(1)---开发板测试
  • 【Linux】动/静态库
  • 重生之我在学Vue--第10天 Vue 3 项目收尾与部署
  • Unity Lerp和InverseLerp函数用处
  • 【C++】每日一练(用队列实现栈)
  • 【fnOS飞牛云NAS本地部署跨平台视频下载工具MediaGo与远程访问下载视频流程】
  • VS Code 配置优化指南
  • 【TES817】基于XCZU19EG FPGA的高性能实时信号处理平台
  • 【从零开始学习计算机科学】数据库系统(七)并发控制技术
  • 元宇宙与数字孪生
  • 如何查看mysql某个表占用的空间大小
  • 深度学习 bert流程
  • ClickHouse的数据引擎:解锁大数据分析的奥秘
  • Netty基础—4.NIO的使用简介二
  • 工控hmi医疗终端机的界面如何来设计?本文为你解答
  • GolangTCP通信解决粘包问题
  • JAVA中的多线程安全问题及解决方案