算法基础之最长上升子序列 II

2023-12-25 18:31:49

最长上升子序列 II

  • 核心思想:不去遍历全部的数据(会有冗余)

    • 用vector模拟栈 ①如果该元素大于栈顶元素,将该元素入栈

    • ②替换掉第一个大于或者等于这个数字的那个数(二分)

      在这里插入图片描述

  •   #include<iostream>
      #include<algorithm>
      #include<vector>
      
      using namespace std;
      int n;
      
      int main()
      {
          cin>>n;
          vector<int> a(n),stk;  //a(n) 必须这么写才能用a[]操作数据
          for(int i=0;i<n;i++) cin>>a[i];  //输入数据
          
          stk.push_back(a[0]);  //a[0] 入栈初始化
          for(int i=1;i<n;i++)  //从a[1] 开始
          {
              if(a[i] > stk.back()) stk.push_back(a[i]);  //大于栈顶元素 直接加进去
              else
              {	//二分 lower_bound从头找出>=a[i]的第一个元素 将其替换(函数返回指针 解引用)
                  *lower_bound(stk.begin(),stk.end(),a[i]) = a[i];
              }
          }
          
          cout<<stk.size()<<endl;  //stk内容不一定是目标子序列 但是长度没问题
      }
    
    • 注意a的定义写法
      • 在这里插入图片描述
  • 参考题解 : https://www.acwing.com/solution/content/3783/

文章来源:https://blog.csdn.net/Pisasama/article/details/135205037
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。