核心思想
引入ends数组，里面将依次存储一个递增的数字，
每当i进行遍历到新的数字时，那么就要将其在其中查找到>=当前数值的最小值，并替换掉它，找不到就将当前值放在ends数组的最后一位
在ends数组中，在当前值之前的数值，一来比当前值小，而来位置在当前数值前面，满足子序列的要求
并且由于ends数组的存储方式，ends数组将为递增的，可以用二分搜索加速查找过程
但是要注意的是ends数组最后只能表示最长的子序列是什么样子的，无法对应每个位置的子序列
题目四和题目五的分离技巧
例题
1、最长递增子序列
题目描述： 给你一个整数数组 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
进阶：
你能将算法的时间复杂度降低到
O(n log(n))吗?
题解
最初的解法是直接定义dp[i]表示必须以i位置结尾的最长递增子序列长度
那么每次遍历到一个数字就需要与之前遍历过的数字比较，
若当前>之前的数字，则当前位置结尾的子序列长度=被比较的数字的最长子序列长度+1，最后选取最大的那个
时间复杂度为O (n^2)
上面的解法虽然能通过，但是时间复杂度高，原因在于每次都要回头进行比较，那么能不能以一个方式优化这个比较的过程
因此我们就引入了ends数组，里面将依次存储一个递增的数字，
每当i进行遍历到新的数字时，那么就要将其在其中查找到>=当前数值的最小值，并替换掉它，找不到就将当前值放在ends数组的最后一位
在ends数组中，在当前值之前的数值，一来比当前值小，而来位置在当前数值前面，满足子序列的要求
并且由于ends数组的存储方式，ends数组将为递增的，可以用二分搜索加速查找过程
但是要注意的是ends数组最后只能表示最长的子序列是什么样子的，无法对应每个位置的子序列
代码如下
package main.java.class072;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code01_LongestIncreasingSubsequence
* @description: 最长递增子序列和最长不下降子序列
* // 给定一个整数数组nums
* // 找到其中最长严格递增子序列长度、最长不下降子序列长度
* // 测试链接 : https://leetcode.cn/problems/longest-increasing-subsequence/
* @author: zs宝
* @create: 2025-08-25 11:06
* @Version 1.0
**/public class Code01_LongestIncreasingSubsequence {
class Solution {
public int lengthOfLIS(int[] nums) {
return lengthOfLIS2(nums);
}
/**
最普通的动态规划解法
*/
public int lengthOfLIS1(int[] nums) {
int n = nums.length;
//dp[i]表示必须以i位置结尾的最长递增子序列长度
int[] dp = new int[n];
int ans = 0;
for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
ans = Math.max(ans, dp[i]);
}
return ans;
}
//有普通版优化后的解法
public int lengthOfLIS2(int[] nums) {
int n = nums.length;
// len表示ends数组目前的有效区长度
// ends[0...len-1]是有效区，有效区内的数字一定严格升序
int[] ends = new int[n];
int len = 0;
for (int i = 0, find; i < n; i++) {
//利用二分搜索查找出>=nums[i]的第一个位置
find = bs1(ends, len, nums[i]);
if (find == -1) {
//没找到说明这个ends中没有比它大的值，可以放在最后面
ends[len++] = nums[i];
} else {
ends[find] = nums[i];
}
}
return len;
}
// "最长递增子序列"使用如下二分搜索 : // ends[0...len-1]是严格升序的，找到>=num的最左位置
// 如果不存在返回-1
public int bs1(int[] ends, int len, int num) {
int l = 0;
int r = len - 1;
int medin = 0;
int ans = -1;
while (l <= r) {
medin = (l + r) / 2;
if (ends[medin] >= num) {
ans = medin;
r = medin - 1;
} else {
l = medin + 1;
}
}
return ans;
}
// 如果求最长不下降子序列，那么使用如下的二分搜索 : // ends[0...len-1]是不降序的
// 在其中找到>num的最左位置，如果不存在返回-1
// 如果求最长不下降子序列，就在lengthOfLIS中把bs1方法换成bs2方法
public int bs2(int[] ends, int len, int num) {
int l = 0;
int r = len - 1;
int medin = 0;
int ans = -1;
while (l <= r) {
medin = (l + r) / 2;
if (ends[medin] > num) {
ans = medin;
r = medin - 1;
} else {
l = medin + 1;
}
}
return ans;
}
}
}2、俄罗斯套娃信封问题
题目描述： 给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。
示例 1：
输入：envelopes = [[5,4],[6,4],[6,7],[2,3]] 输出：3 解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
示例 2：
输入：envelopes = [[1,1],[1,1],[1,1]] 输出：1
提示：
1 <= envelopes.length <= 105envelopes[i].length == 21 <= wi, hi <= 105
解题思路：
这个题要求高度宽度都要大于另一个信封才能装下，其实就相当于一个二维要求的最长递增子序列问题
难点就在在于如何将其转化为一维
这里我们可以先将起按照宽度从小打大排序来做，而当宽度等时，就按照高度从大到小排序
为什么这样呢？先将宽度从小到大排序这样就可以在使用一维的方法时，保证从前往后遍历宽度都能被下一个信封尽可能装下
而宽度相同时采用高度从大到小排序，按照题目要求宽度相同的只能选一个信封，那么按照ends的计算要求，后续的较小那一部分一定会将大的那一部分取代，如果从小到大，那么ends数组中大概率会出现宽度相等的信封的不同高度数字在其中，这不符合题意要求。另外选择较小的那个，对于后面不同宽度时，也会让信封套娃可能性更高
在本题和上一题中，我在计算bs的函数中，老是将它ans初始化为0，但是按照主函数的解题思路，应该是-1才行。
代码
package main.java.class072;
import java.util.Arrays;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code02_RussianDollEnvelopes
* @description: 俄罗斯套娃信封问题，
给你一个二维整数数组envelopes ，其中envelopes[i]=[wi, hi]，
表示第 i 个信封的宽度和高度，
当另一个信封的宽度和高度都比这个信封大的时候， 这个信封就可以放进另一个信封里，如同俄罗斯套娃一样， 请计算 最多能有多少个信封能组成一组“俄罗斯套娃”信封，
即可以把一个信封放到另一个信封里面，注意不允许旋转信封 测试链接 : https://leetcode.cn/problems/russian-doll-envelopes/
* @author: zs宝
* @create: 2025-08-26 09:15
* @Version 1.0
**/public class Code02_RussianDollEnvelopes {
class Solution {
public int maxEnvelopes(int[][] envelopes) {
int n=envelopes.length;
//按宽度从小到达排序
//宽度相同时，将高度从大到小排序
Arrays.sort(envelopes,(a, b)->a[0]==b[0]?b[1]-a[1]:a[0]-b[0]);
//排序完成后，后续就按照高度值的顺序，遵照做场递增子序列
//做到了将二维转为一维
int []ends=new int[n];
int len=0;
for(int i=0,num,find;i<n;i++){
num=envelopes[i][1];
find=bs(ends,len,num);
if(find==-1){
ends[len++]=num;
}else{
ends[find]=num;
}
}
return len;
}
/**
二分查找寻找>=num的最小位置
*/
public int bs(int[]ends,int len,int num){
int l=0,r=len-1,medin,ans=-1;
while(l<=r){
medin=(l+r)/2;
if(ends[medin]>=num){
ans=medin;
r=medin-1;
}else{
l=medin+1;
}
}
return ans;
}
}
}3、使数组K递增的最少操作次数
题目描述： 给你一个下标从 0 开始包含 n 个正整数的数组 arr ，和一个正整数 k 。
如果对于每个满足 k <= i <= n-1 的下标 i ，都有 arr[i-k] <= arr[i] ，那么我们称 arr 是 K 递增 的。
比方说，
arr = [4, 1, 5, 2, 6, 2]对于k = 2是 K 递增的，因为：arr[0] <= arr[2] (4 <= 5)arr[1] <= arr[3] (1 <= 2)arr[2] <= arr[4] (5 <= 6)arr[3] <= arr[5] (2 <= 2)
但是，相同的数组
arr对于k = 1不是 K 递增的（因为arr[0] > arr[1]），对于k = 3也不是 K 递增的（因为arr[0] > arr[3]）。
每一次 操作 中，你可以选择一个下标 i 并将 arr[i] 改成任意 正整数。
请你返回对于给定的 k ，使数组变成 K 递增的 最少操作次数 。
示例 1：
输入：arr = [5,4,3,2,1], k = 1 输出：4 解释： 对于 k = 1 ，数组最终必须变成非递减的。 可行的 K 递增结果数组为 [5,6,7,8,9]，[1,1,1,1,1]，[2,2,3,4,4] 。它们都需要 4 次操作。 次优解是将数组变成比方说 [6,7,8,9,10] ，因为需要 5 次操作。 显然我们无法使用少于 4 次操作将数组变成 K 递增的。
示例 2：
输入：arr = [4,1,5,2,6,2], k = 2 输出：0 解释： 这是题目描述中的例子。 对于每个满足 2 <= i <= 5 的下标 i ，有 arr[i-2] <= arr[i] 。 由于给定数组已经是 K 递增的，我们不需要进行任何操作。
示例 3：
输入：arr = [4,1,5,2,6,2], k = 3 输出：2 解释： 下标 3 和 5 是仅有的 3 <= i <= 5 且不满足 arr[i-3] <= arr[i] 的下标。 将数组变成 K 递增的方法之一是将 arr[3] 变为 4 ，且将 arr[5] 变成 5 。 数组变为 [4,1,5,4,6,5] 。 可能有其他方法将数组变为 K 递增的，但没有任何一种方法需要的操作次数小于 2 次。
提示：
1 <= arr.length <= 1051 <= arr[i], k <= arr.length
解题思路：
题目问的是最少操作次数
而这个操作数来自于你数组中每一轮的i, i+k, i+2k,........... 形成的另外的数组
而来这样的数组中要求都有
arr[i-k] <= arr[i]（注意这里相等也可以），那么要让这个新形成的数组变成符合题意的样子，且操作次数最小那么可以用这个新形成数组的长度-其最长不下降子序列
那么总得最少操作次数=每轮的做少操作数之和
代码
package main.java.class072;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code03_MinimumOperationsToMakeArraykIncreasing
* @description: 使数组K递增的最少操作次数，
* 给你一个下标从0开始包含n个正整数的数组arr，和一个正整数k，
* 如果对于每个满足 k <= i <= n-1 的下标 i，
* 都有 arr[i-k] <= arr[i] ，那么称 arr 是K递增的，
* 每一次操作中，你可以选择一个下标i并将arr[i]改成任意正整数，
* 请你返回对于给定的 k ，使数组变成K递增的最少操作次数
* 测试链接 : https://leetcode.cn/problems/minimum-operations-to-make-the-array-k-increasing/
* @author: zs宝
* @create: 2025-08-26 09:31
* @Version 1.0
**/public class Code03_MinimumOperationsToMakeArraykIncreasing {
class Solution {
public static int MAXLEN=100001;
//用于存储每一轮的k递增数
public static int []nums=new int[MAXLEN];
public static int[]ends=new int[MAXLEN];
public static int kIncreasing(int[] arr, int k) {
int n=arr.length;
int ans=0;
//将数组中所有可以形成i i+k i+2k。。。的数字放于num数组中去
for(int i=0,size;i<k;i++){
size=0;
for(int j=i;j<n;j+=k){
nums[size++]=arr[j];
}
//求出形成i i+k i+2k。。。的数字放于num数组中的不下降子序列，用总得长度-不下降子序列的长度=需要操作的数
ans+=size-lengthOfNoDecreasing(size);
}
return ans;
}
/**
求nums数组中0,size-1的数中最长不下降子序列长度
*/
public static int lengthOfNoDecreasing(int size){
int len=0;
for(int i=0,find;i<size;i++){
find=bs(len,nums[i]);
if(find==-1){
ends[len++]=nums[i];
}else{
ends[find]=nums[i];
}
}
return len;
}
public static int bs(int len,int num){
int l=0,r=len-1,medin,ans=-1;
while(l<=r){
medin=(l+r)/2;
if(ends[medin]>num){
ans=medin;
r=medin-1;
}else{
l=medin+1;
}
}
return ans;
}
}
}4、最长数对链
题目要求 给你一个由 n 个数对组成的数对数组 pairs ，其中 pairs[i] = [lefti, righti] 且 lefti < righti 。
现在，我们定义一种 跟随 关系，当且仅当 b < c 时，数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面。我们用这种形式来构造 数对链 。
找出并返回能够形成的 最长数对链的长度 。
你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
示例 1：
输入：pairs = [[1,2], [2,3], [3,4]] 输出：2 解释：最长的数对链是 [1,2] -> [3,4] 。
示例 2：
输入：pairs = [[1,2],[7,8],[4,5]] 输出：3 解释：最长的数对链是 [1,2] -> [4,5] -> [7,8] 。
提示：
n == pairs.length1 <= n <= 1000-1000 <= lefti < righti <= 1000
解题思路：
这个题目与我们的第二题有些类似指出，但是又不完全相同
我们先将整个数组利用数对的第一个数进行从小到大的排序
然后每次进行最长递增子序列的查找时，用数对的第一个数查找，但是在插入时用数对的第二个数进行插入
不过这里根据题意，在插入时要选择插入值与原值的较小值插入
为什么可以这样？
按照题目要求
b < c，那么首先我们需要根据最左边排序，的到一份粗略的的可能行结果然后每次插入时，插入的是第二个数字，但是查找时，用的是第一个数字，也就满足了
b < c的条件
代码如下：
package main.java.class072;
import java.util.Arrays;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code04_MaximumLengthOfPairChain
* @description:
* @author: zs宝
* @create: 2025-08-26 10:09
* @Version 1.0
**/public class Code04_MaximumLengthOfPairChain {
class Solution {
/**
用dp的最长递增子序列问题求解
*/
public int findLongestChain1(int[][] pairs) {
int n=pairs.length;
//按照最左边的位置由小到大排序
Arrays.sort(pairs,(a, b)->a[0]-b[0]);
int []ends=new int[n];
int len=0;
for(int i=0,find;i<n;i++){
find=bs(ends,len,pairs[i][0]);
//这里用到了查询与插入的分离技巧，这是最长递增子序列类问题的一种常见手段
if(find==-1){
ends[len++]=pairs[i][1];
}else{
ends[find]=Math.min(ends[find],pairs[i][1]);
}
}
return len;
}
public int bs(int[]ends,int len,int num){
int l=0,r=len-1,medin,ans=-1;
while(l<=r){
medin=(l+r)/2;
if(ends[medin]>=num){
ans=medin;
r=medin-1;
}else{
l=medin+1;
}
}
return ans;
}
/**
贪心的解法：最优解
*/
public int findLongestChain(int[][] pairs) {
int n=pairs.length;
//按照最右边的位置由小到大排序
Arrays.sort(pairs,(a,b)->a[1]-b[1]);
int pre=Integer.MIN_VALUE;
int ans=0;
for(int []pair:pairs){
if(pre<pair[0]){
ans++;
pre=pair[1];
}
}
return ans;
}
}
}5、最长不下降子序列
题目描述： 题目描述 给定一个长度为 N 的整数序列：A_{1}, A_{2}, \cdots, A_{N}。现在你有一次机会，将其中连续的 K 个数修改成任意一个相同值。请你计算如何修改可以使修改后的数列的最长不下降子序列最长，请输出这个最长的长度。
最长不下降子序列是指序列中的一个子序列，子序列中的每个数不小于在它之前的数。 输入格式
输入第一行包含两个整数 N 和 K 。
第二行包含 N 个整数 A_{1}, A_{2}, \cdots, A_{N} 。
输出格式
输出一行包含一个整数表示答案。
输入输出样例 #1
输入 #1
5 1
1 4 2 8 5输出 #1
4说明/提示
对于 20 \% 的评测用例, 1 \leq K \leq N \leq 100;
对于 30 \% 的评测用例, 1 \leq K \leq N \leq 1000;
对于 50 \% 的评测用例, 1 \leq K \leq N \leq 10000;
对于所有评测用例, 1 \leq K \leq N \leq 10^{5}, 1 \leq A_{i} \leq 10^{6} 。
解题思路：
将数组分为3个部分，k值区域，k区域左边的最长递增子序列（小于k复制的数），k区域右边的最长递增子序列
k区域右边的最长递增子序列=从n-1位置开始向前的最长不上升子序列
循环数组中的这个k区域，取最大值
代码如下
package main.java.class072;
import java.io.*;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code05_LongestNoDecreaseModifyKSubarray
* @description: 有一次修改机会的最长不下降子序列，
* 给定一个长度为n的数组arr，和一个整数k，
* 只有一次机会可以将其中连续的k个数全修改成任意一个值，
* 这次机会你可以用也可以不用，请返回最长不下降子序列长度，
* 1 <= k, n <= 10^5，
* 1 <= arr[i] <= 10^6，
* 测试链接 : https://www.luogu.com.cn/problem/P8776
* @author: zs宝
* @create: 2025-08-26 11:05
* @Version 1.0
**/public class Code05_LongestNoDecreaseModifyKSubarray {
public static int MAXN = 100001;
public static int[] arr = new int[MAXN];
public static int[] right = new int[MAXN];
public static int[] ends = new int[MAXN];
public static int n, k;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in = new StreamTokenizer(br);
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
while (in.nextToken() != StreamTokenizer.TT_EOF) {
n = (int) in.nval;
in.nextToken();
k = (int) (in.nval);
for (int i = 0; i < n; i++) {
in.nextToken();
arr[i] = (int) in.nval;
}
if (k >= n) {
out.println(n);
} else {
out.println(compute());
}
}
out.flush();
out.close();
br.close();
}
public static int compute() {
right();
int len=0;
int ans=0;
for(int i=0,j=k,left,find;j<n;i++,j++){
//看右边的数可以让k区域前面的多少数形成递增子序列
find=bs2(len,arr[j]);
left=find==-1?len:find;
ans=Math.max(ans,left+k+right[j]);
//找到当前k区域的左边界加入最长子序列的ends中没因为下一轮k区域将刚好不再覆盖它，
// 但是寻找k区域右边的数的在左边可以形成最长递增子序列还需要 加入这个数进行判定
find=bs2(len,arr[i]);
if(find==-1){
ends[len++]=arr[i];
}else{
ends[find]=arr[i];
}
}
ans=Math.max(ans,len+k);
return ans;
}
// 生成辅助数组right
// right[j] : // 一定以arr[j]做开头的情况下，arr[j...]上最长不下降子序列长度是多少
// 关键逻辑 : // 一定以arr[i]做开头的情况下，arr[i...]上最长不下降子序列
// 就是！从n-1出发来看(从右往左遍历)，以arr[i]做结尾的情况下的最长不上升子序列
public static void right() {
int len=0;
for(int i=n-1,find;i>=0;i--){
find=bs1(len,arr[i]);
if(find==-1){
ends[len++]=arr[i];
right[i]=len;
}else{
ends[find]=arr[i];
right[i]=find+1;
}
}
}
// 求最长不上升子序列长度的二分
// ends[0...len-1]是降序的，找到<num的最左位置
// 不存在返回-1
public static int bs1(int len, int num) {
int l = 0, r = len - 1, m, ans = -1;
while (l <= r) {
m = (l + r) / 2;
if (ends[m] < num) {
ans = m;
r = m - 1;
} else {
l = m + 1;
}
}
return ans;
}
// 求最长不下降子序列长度的二分
// ends[0...len-1]是升序的，找到>num的最左位置
// 不存在返回-1
public static int bs2(int len, int num) {
int l = 0, r = len - 1, m, ans = -1;
while (l <= r) {
m = (l + r) / 2;
if (ends[m] > num) {
ans = m;
r = m - 1;
} else {
l = m + 1;
}
}
return ans;
}
}